Hashtable

实现

• hashtable采用桶位+链表结构实现。

  
  image.png

image.png

put操作

image.png

• 可以看出value为null时，会抛空指针异常，key为null时，调用hashCode()方法也会报空指针异常，key和value不允许为null;

image.png

• 如果实际大小count大于阀值，需要rehash，调整整个table；
• 根据索引位置，获取索引元素；
• 使用新添加的元素作为该索引位置的头节点，老元素作为后继节点。

rehash操作

image.png

• 扩容大小为原来的2倍+1；
• 从后往前循环遍历数组元素；
• 对遍历到的元素节点进行遍历，将指定索引位置i的老元素作为重新hash后的元素的后继节点（即e.next = (Entry<K,V>)newMap[index];），最后将新hash到元素作为索引位置i处的头节点。

get操作

image.png

• 根据key的hashcode的低31位和数组的长度取余索引元素。

remove操作

image.png

replace操作

image.png

遍历