1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
|
public class <K, V> { private static final int upperTol = 10; private static final int lowerTol = 2; private static final int initCapacity = 7;
private TreeMap<K, V>[] hashTable; private int M; private int size;
public (int m) { M = m; size = 0; hashTable = new TreeMap[M]; for (int i = 0; i < M; i++) { hashTable[i] = new TreeMap<>(); } }
public () { this(initCapacity); }
private int hash(K key) { return (key.hashCode() & 0x7fffffff) % M; }
public int getSize() { return size; }
public void add(K key, V value) { TreeMap<K, V> map = hashTable[hash(key)]; if (map.containsKey(key)) { map.put(key, value); } else { map.put(key, value); size++; if (size >= upperTol * M) { resize(2 * M); } } }
public V remove(K key) { TreeMap<K, V> map = hashTable[hash(key)]; V ret = null; if (map.containsKey(key)) { ret = map.remove(key); size--; if (size < lowerTol * M && M / 2 > initCapacity) { resize(M / 2); } } return ret; }
private void resize(int newM) { TreeMap<K, V>[] newHashTable = new TreeMap[newM]; for (int i = 0; i < newM; i++) { newHashTable[i] = new TreeMap<>(); } int oldM = M; this.M = newM; for (int i = 0; i < oldM; i++) { TreeMap<K, V> map = hashTable[i]; for (K k : map.keySet()) { newHashTable[hash(k)].put(k, map.get(k)); } } this.hashTable = newHashTable; }
public void set(K key, V value) { TreeMap<K, V> map = hashTable[hash(key)]; if (!map.containsKey(key)) { throw new IllegalArgumentException(key + "doesn't exist!"); } map.put(key, value); }
public boolean contains(K key) { return hashTable[hash(key)].containsKey(key); }
public V get(K key) { TreeMap<K, V> map = hashTable[hash(key)]; if (!map.containsKey(key)) { throw new IllegalArgumentException(key + "doesn't exist!"); } return map.get(key); } }
|
近期评论