-
hashmap的hashcode计算
1.7 9次扰动处理=4次位运算+5次异或
1.8 2次扰动处理=1次位运算+1次异或
-
扩容时的hashcode有什么变化?
1.7 hashcode--->>扰动处理--->>重新和(新容量-1)相&
1.8直接利用了这个特性,元素的位置等于原位置或者原位置+旧容量,这种方法只需要判断新参与&运算的位计算结果是0还是1就可以解决,
-
hashmap底层结构
1.7数组+单链表
1.8数组+单链表+红黑树
-
为什么数组大小一定是2的幂次?
- HashMap的长度为2的幂次方的原因是为了减少Hash碰撞，尽量使Hash算法的结果均匀分布,计算公式是hashcode%(n-1),当n是2的幂次时,n-1的二进制所有位均为1,这样计算出来的位置只和传入数据的hashcode有关联,如果非2的幂次,比如10,那么n-1等于9,10001,必然会存在概率不平均的问题
-
如果hashmap构造参数传入17,他的容量是怎么计算成32的?
先将值-1(避免传进来的值就是2的幂次,比如如果是4,会算出来8),然后不断移位并与自身或
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;</pre>return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
最后返回计算出来的n+1
-
为什么引入红黑树?
- 在数据为8的时候折叠成红黑树,时间复杂度为(logn)级别,显然优于链表的O(n)
-
为什么用rb,不用bst,avl?
首先bst极端条件会链化
avl解决了链化的问题,但是频繁的插入删除会让他不断地左旋右旋,性能大打折扣
红黑树不是严格的avl,他的查找性能低于avl,但是查找插入会优于avl
-
那谈谈红黑树吧?
-
既然红黑树那么好,为什么不直接使用红黑树,还要用链表呢?
- "因为树节点的大小是链表节点大小的两倍，所以只有在容器中包含足够的节点保证使用才用它”，显然尽管转为树使得查找的速度更快，但是在节点数比较小的时候，此时对于红黑树来说内存上的劣势会高于查找的操作
-
为什么HashMap树化的临界值为什么是8，链化的链接值为6,为什么不是9,10?那为什么不取7,不取6呢?
根据泊松分布,桶的长度超过8的概率为亿分之六,小于千万分之一,极低,再往后调整就没多大意义了
7作为中间的过度点,这个时候链表和红黑树综合比较差别不大,避免频繁的链表和红黑树
-
hashmap元素插入方式
1.7头插法
1.8尾插法
-
为什么改为尾插?
- 尾插可以解决并发扩容的时候出现逆序和环路的问题,但是之前的头插也很方便,比如:头插就不用像尾插一样,需要一路遍历链表到最后找到最后一个节点再插入,并且刚刚插入的数据,有很大的可能又被作为头部快速的拿出来.
-
hashmap扩容方式
1.7 扩容后插入元素
1.8 扩容前插入元素
-
为什么1.7扩容前插入,1.8扩容后插入?不明白
-
为什么hashmap的key和value都允许为null?
hashmap key为null的hashcode为0,全部放入数组0序号中,只能有一个key为null
hashmap是非线程安全的,不适用于并发,所以他有containsKey()这个方法,来判断key是否存在,如果是线程安全的类比如hashtable他就不支持key为null,为了保证并发安全就没有containsKey()这个方法,只能通过getKey()来判断key是否为null,但是如果允许key为null,那当getKey()返回null,我无法判断是key的值为null,还是key不存在所以返回null
-
为什么hashmap是线程不安全的?
没有同步锁保护
1.7中头插法的存在会出现环形链表,在遍历数据的时候形成死循环
hashmap迭代器的fail-fast策略,并发修改时,出现modcount和expectedModCount出现不一致抛出
ConcurrentHashModificationException异常
-
那如果多线程操作hashmap会遇到什么问题?
1.7版本由于是头插法,不断put(),出现环形链表,导致get()陷入死循环
put()如果操作同一个数组下标可能出现数据丢失和覆盖
-
为什么hashmap不保证有序?
- 插入顺序和存储顺序不同,插入顺序是用户操作的顺序,存储顺序是根据hash算法计算的数组下标
-
为什么hashmap存储位置随时间变化?
- 其实是随着扩容操作而变化,扩容会使存储位置重新计算
-
为什么hashmap中String,Integer这种包装类更适合作为key?
因为这种包装类,保证了hash值的不可变性--->>包装类被final修饰
有效减少了hash碰撞--->>内部重写了hashcode和equals不易出现hash的计算错误
-
hashmap的key若为Object,则需要实现哪些方法?
- hashcode()和equals()
后续问题:
hashmap既然线程不安全的,那你怎么解决这个问题?(HashTable,Collections.synchronizedMap(),ConcurrentHashMap)
-
HashMap内部既然是无序的,那有没有有序的map?
(LinkedHashMap,TreeMap)
