HashTable

HashTable

1.put

    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        addEntry(hash, key, value, index);
        return null;
    }

• put是被synchronize修饰的方法，所以是线程安全的。

当第一次使用时，会根据key创建一个entry，并放在对象数组table中，结构如下

并且next执行空。

当第二次put时，

• 如果经计算后hash值不同，会从新生成一个entry并放在数组table中，结构如下

• 

• 如经计算后hash相同而key值不相同。 会获取table中hash值相同的entry，假设table[1];然后创建一个新的entry，并让新的entry中的next指向table[1],再把table[1]指向新创建的entry。相当于新的entry把原来的entry顶出数组。结构如下

  
  

• 

2.get

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

• 0x7FFFFFFF
  为16进制4个字节的1，最后一位为符号为所以是7。即0111 1111 1111 1111 1111 1111 1111 1111

• &
   与运算 当同为1时，才为1。在这里是为了防止hash值为负数。不用绝对值函数的原因是最大负数没有正数。

通过for循环遍历列表，找到则返回。

重要提示
：put和get都是用 synchronized
关键字来解决并发问题。

3.rehash

当put时，会判断entry个数是否超出了负载因子，如果超出进行rehash操作。

 if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

• rehash()

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

• intnewCapacity=(oldCapacity<<1)+1;
   扩大两倍加一。加一是为了防止一直为0的现象。

• 如果超过最大值，则使用最大值做为 newCapacity
  。

• 通过遍历把old entry重新排序。