Subversion Repositories programming

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
5 irasnyd 1 
//import chap09.list03.Map;
2 
 
3 
import java.io.*;
4 
import java.util.*;
5 
 
6 
public class HashTable implements Map {  // open addressing
7 
    private Entry[] entries;
8 
    private int size, used;
9 
    private float loadFactor;
10 
    private final Entry NIL = new Entry(null,null);  // dummy
11 
 
12 
    public HashTable(int capacity, float loadFactor) {
13 
        entries = new Entry[capacity];
14 
        this.loadFactor = loadFactor; }
15 
 
16 
    public HashTable(int capacity) {
17 
        this(capacity,0.75F);}
18 
 
19 
    public HashTable() {
20 
        this(101); }
21 
 
22 
    public Object get(Object key) {
23 
        int h=hash(key);
24 
        for (int i=0; i<entries.length; i++) {
25 
            int j = nextProbe(h,i);
26 
            Entry entry=entries[j];
27 
            if (entry==null) break;
28 
            if (entry==NIL) continue;
29 
            if (entry.key.equals(key)) return entry.value;  // success
30 
        }
31 
        return null;  // failure: key not found
32 
    }
6 irasnyd 33 
 
5 irasnyd 34 
    public Object put(Object key, Object value) {
35 
        if (used>loadFactor*entries.length) rehash();
36 
        int h=hash(key);
37 
        for (int i=0; i<entries.length; i++) {
38 
            int j = nextProbe(h,i);
39 
            Entry entry=entries[j];
40 
            if (entry==null) {
41 
                entries[j] = new Entry(key,value);
42 
                ++size;
43 
                ++used;
44 
                return null;  // insertion success
45 
            }
46 
            if (entry==NIL) continue;
47 
            if (entry.key.equals(key)) {
48 
                Object oldValue=entry.value;
49 
                entries[j].value = value;
50 
                return oldValue;  // update success
51 
            }
52 
        }
53 
        return null;  // failure: table overflow
54 
    }
55 
 
56 
    public Object remove(Object key) {
57 
        int h=hash(key);
58 
        for (int i=0; i<entries.length; i++) {
59 
            int j = nextProbe(h,i);
60 
            Entry entry=entries[j];
61 
            if (entry==null) break;
62 
            if (entry==NIL) continue;
63 
            if (entry.key.equals(key)) {
64 
                Object oldValue=entry.value;
65 
                entries[j] = NIL;
66 
                --size;
67 
                return oldValue;  // success
68 
            }
69 
        }
70 
        return null;  // failure: key not found
71 
    }
72 
 
73 
    public int size() {
74 
        return size;
75 
    }
76 
 
77 
    private class Entry {
78 
        Object key, value;
79 
        Entry(Object k, Object v) { key=k; value=v; }
80 
    }
81 
 
82 
    private int hash(Object key) {
83 
        if (key==null) throw new IllegalArgumentException();
84 
        return (key.hashCode() & 0x7FFFFFFF) % entries.length;
85 
    }
86 
 
87 
    private int nextProbe(int h, int i) {
88 
        return (h + i)%entries.length;      // Linear Probing
89 
    }
90 
 
91 
    private void rehash() {
92 
        Entry[] oldEntries = entries;
93 
        entries = new Entry[2*oldEntries.length+1];
94 
        for (int k=0; k<oldEntries.length; k++) {
95 
            Entry entry=oldEntries[k];
96 
            if (entry==null || entry==NIL) continue;
97 
            int h=hash(entry.key);
98 
            for (int i=0; i<entries.length; i++) {
99 
                int j = nextProbe(h,i);
100 
                if (entries[j]==null) {
101 
                    entries[j] = entry;
102 
                    break;
103 
                }
104 
            }
105 
        }
106 
        used = size;
107 
    }
108 
}