Hashtable 的实现原理

1 基本原理

  我们使用一个下标范围比较大的数组，它通过一个结构体Entry来表示哈希表中的单个元素，这个结构体中有四个成员：
（1）key ：表示键，即哈希表中的关键字。
（2）val ：表示值，即跟关键字所对应值。
（3）Entry<K,V> next ：指向下一个Entry,(主要用来解决冲突)
（4）hash ：它是一个int类型，用于表示键所对应的哈希码来存储元素
数组的Entry的存放位置index是根据 h & (length-1) 其中h为key的hash值，lenth为数组的大小，也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。数组初始大小为8，当元素大于或等于数组的threshold就重新new一个length为当前数组两倍的新数组，旧的数组里的数据需要转换的新的数组:
void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
               
            }
        }
    }
但是，index不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。

2.解决冲突
void addEntry(int hash, K key, V value, int index) {
Entry<K,V> e = table[index];
        table[index] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
        }
}
3.获取数据
public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
        e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }