【数据结构】9.java源码关于HashTable

1.hashtable的内部结构

基础存储数据的hash桶由Entry结构的数组存放
而entry数据结构，有hash，key和value，还有一个指向下一个节点的引用next对象

这里就和hashmap中的数据结构不一样了，hashmap中的数据结构是node，虽然结构上差不多，但是setvalue的非空判断和hashcode的散列取值都是和node不一样的

那么这些数据在什么时候用呢？？？
下面来一一了解

2.hashtable的构造函数

这里需要注意一下了，我们前面提到说hashmap中的构造函数，其实实际上是不对hash桶进行实例化的，但是hashtable不一样，他会直接实例化大小，并且实例化成你指定的大小
而且这里默认的初始化容器的大小是11，负载因子代销默认0.75，负载因子的作用就是规定最大容量：hash桶的大小*负载因子

public TestHashTable(int initialCapacity, float loadFactor) {

    //非空判断

    if (initialCapacity < 0)

        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);

    if (loadFactor <= 0 || Float.isNaN(loadFactor))

        throw new IllegalArgumentException("Illegal Load: " + loadFactor);

    //至少设置为1

    if (initialCapacity==0)

        initialCapacity = 1;

    this.loadFactor = loadFactor;

    table = new Entry<?,?>[initialCapacity];

    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

}

3.hashtable的增加元素策略

1.这里的put方法加了synchronized修饰符，用来标识线程安全
2.这里进行put取索引位置的时候，是直接用的key的hashcode方法，并且对hashcode结果进行取正数(& 0x7FFFFFFF)，然后对hash桶进行取余%
然后就是判断这个key是否存在于这个hash桶中，如果存在更新旧值，并返回旧值
不存在，那么就添加一个entry，所以put操作的关键就是addEntry

而我们add操作其实就是找到对应的散列位置，然后用头插法

private void addEntry(int hash, K key, V value, int index) {

    modCount++;

    Entry<?,?> tab[] = table;

    if (count >= threshold) {

        // Rehash the table if the threshold is exceeded

        rehash();

        tab = table;

        hash = key.hashCode();

        index = (hash & 0x7FFFFFFF) % tab.length;

    }

    // Creates the new entry.

    @SuppressWarnings("unchecked")

    Entry<K,V> e = (Entry<K,V>) tab[index];

    //头插法

    tab[index] = new Entry<>(hash, key, value, e);

    count++;

}

说实话，这里相比hashmap来说简单多了，主要是少了树化的操作

4.hashtable删除元素策略

删除就比较简单了，就是找到对应的索引位置，然后再查找链表，如果是头节点，直接把entry.next设置为索引位置的数据，如果不是，就要获取到pre节点，然后pre.next = entry.next

public synchronized V remove(Object key) {

    Entry<?,?> tab[] = table;

    int hash = key.hashCode();

    int index = (hash & 0x7FFFFFFF) % tab.length;

    @SuppressWarnings("unchecked")

    Entry<K,V> e = (Entry<K,V>)tab[index];

    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {

        if ((e.hash == hash) && e.key.equals(key)) {

            modCount++;

            if (prev != null) {

                prev.next = e.next;

            } else {

                tab[index] = e.next;

            }

            count--;

            V oldValue = e.value;

            e.value = null;

            return oldValue;

        }

    }

    return null;

}

主要是for循环这个地方有点意思，其余的到还好，无非就是返回旧值而已

5.修改元素，查找元素

修改不多做操作了，和添加，删除操作差不多，只是没有里面的多余操作，就是找到元素就直接返回了

6.hashtable特殊操作

1.hashtable是允许放空键值的，也就是键和值都可以放null
2.还有hashtable是线程安全的
3.hashmap再1.8之后是数组+链表+红黑树，hashtable还是很光棍-》数组+链表
4.扩容需要说一下，hashmap会扩容到比设置值大的最小2次幂，hashtable就群魔乱舞随意了
5.hashmap和hashtable都是取余，但是有点不同，因为hashmap是2次幂，所以取余的方式不一样是：(n - 1) & hash,为什么这样，请复习hashmap源码分析。。。

7.hashtable的刷新扩容

protected void rehash() {

    int oldCapacity = table.length;

    Entry<?,?>[] oldMap = table;

    //直接左移一位，也就是扩大2倍然后+1 =》 大小扩为 2n + 1

    int newCapacity = (oldCapacity << 1) + 1;

    if (newCapacity - MAX_ARRAY_SIZE > 0) { //Integer.MAX_VALUE - 8

        if (oldCapacity == MAX_ARRAY_SIZE) //如果老的容量已经达到这个值，anemia继续保持

            // Keep running with MAX_ARRAY_SIZE buckets

            return;

        newCapacity = MAX_ARRAY_SIZE; //否则设置为允许的最大值

    }

    //创建新的hash桶

    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;

    //设置新的阈值

    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

    table = newMap;

    //遍历hash桶，从后往前

    for (int i = oldCapacity ; i-- > 0 ;) {

        //遍历所有索引下的链表，吧链表添加到新的hash桶上

        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;

        }

    }

}

总结一下吧：

说实话，看完hashtable没花多久时间，相比较hashmap给人的惊为天人的操作，hashtable相对来说就比较朴实无华了，唯一的几个亮点就是线程安全，然后。。。。
想不出来了，只能说存在即合理，不能说hashtable会比较low，也许是我眼拙，大道至简，也许没有那些花里胡哨的才是真正最实用的

参考：
https://juejin.im/post/5a03b258518825188e515d89
https://blog.csdn.net/yyc1023/article/details/80619623

巴特西