Hashtable
2019-06-22 本文已影响0人
那谁319
实现
-
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
遍历
