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 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
| package com.holelin.tree;
import java.util.TreeMap;
public class HashTable<K, V> { private final int[] capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}; private TreeMap<K, V>[] hashtable; private int M; private int size;
private static final int upperTol = 10;
private static final int lowerTol = 2;
private int capacityIndex = 0;
public HashTable() { this.M = capacity[capacityIndex]; this.size = 0; hashtable = new TreeMap[M]; for (int i = 0; i < hashtable.length; i++) { hashtable[i] = new TreeMap<>(); } }
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 && capacityIndex + 1 < capacity.length) { capacityIndex++; resize(capacity[capacityIndex]); } }
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 key : map.keySet()) { newHashTable[hash(key)].put(key, map.get(key)); } } this.hashtable = newHashTable; }
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 && capacityIndex - 1 >= 0) { capacityIndex--; resize(capacity[capacityIndex]); } return ret; }
public void set(K key, V value) { TreeMap<K, V> map = hashtable[hash(key)]; if (!map.containsKey(key)) { throw new IllegalArgumentException(key + "does't exist"); } map.put(key, value); }
public boolean contains(K key) { return hashtable[hash(key)].containsKey(key); }
public V get(K key) { return hashtable[hash(key)].get(key); }
}
|