hash表
思考
- 在实现代码中, 我们使用了尾插法, 如果改成头插法呢?
也可以, 在java1.8之前时, hashMap采用的是头插法, 但是在多线程环境下会出现死循环的问题.后来1.8改用了尾插法.
- JDK的HashMap中采用了将对象HashCode高低位相互异或的方式减少冲突,怎么理解?
在我们的数组长度为为2^n次方的情况下, 一个特别大的数与一个特别小的数,就会很容易产生冲突. 这种方式能减少这种冲突.
- 我们的HashTable中表格容量是2的n次方,很多优化都是基于这个前提,能否不用2的n次方作为表格容量?
可以, jdk自带的HashTable的实现, 就是以11作为Table的容量.
- JDK的HashMap在链表中长度过长时(为8时),会转换为红黑树,对此怎么看.
经过我们使用hashCode的散列算法时, 20万的数据中最长的链表是6, 如果想要出现链表为8的情况, 会需要更多的数据.
一般是遭到了对方的攻击,持续的添加同一散列位置的key, 而转换为红黑树就是为了防止这种情况的发生, 在这种情况下依然能够正常运行.