HashMap分为JDK1.7和JDK1.8两个版本,JDK1.7使用的是数组加链表的形式进行数据的存储,而JDK1.8则采用数组加链表加红黑树的形式. JDK1.7中 使用Entry节点进行(key,value)的存储,数组默认长度是16,采用(hash值(这里hash值经过右位移和异或运算))&(数组长度-1)的方式来确定index,若index值相同,这种情况称为哈希碰撞,解决哈希碰撞的方法是头插法;在多线程的情况下,会产生循环链表的问题(传说中的死循环). 1.为什么采用头插法? 头部插入不需要遍历链表,节省效率;新节点插入头部后,将新节点移动到数组上,方便后续使用. 2.数组长度为何取2的次幂的形式? index的计算方法是hash值&(数组长度-1),当length为2的次幂的形式时,可以取到0~(length-1)的所有位置. 3.为什么计算index时使用&操作? JDK1.4之后使用&操作,之前使用%(取余),&操作是基于bit位的计算,更快. 4.解决HashMap中有的链表特别长,影响get的效率的问题 一开始得到的hash值,进行右移,异或运算,这样链表的长度就会变得比较均匀,增强散列性 5.如果put一个已经有的key,HashMap是如何解决的? 底层会进行hash值的比较,若hash值相等,在比较key的值是否相等,若key的值相等,返回旧的key对应的value,存入新的key对应的value. 6.特殊:key=null的时候,会存放在数组下标为0的位置 7.扩容机制? 先扩容再添加元素 在(size >= threshold) && (null != table[bucketIndex])的情况下,将原数组进行2倍扩容,原数组链表上的元素重新进行hash值&(新数组长度-1)运算,放到新数组链表上. (这里转移前的元素的位置为x,转移后的元素的位置为x或x+旧数组长度) JDK1.8 使用Node节点进行(key,value)的存储,数组默认长度是16,采用(hash值(这里hash值经过右位移和异或运算,比1.7简单))&(数组长度-1)的方式来确定index,若index值相同,这种情况称为哈希碰撞,解决哈希碰撞的方法是尾插法. 1.为什么加红黑树? JDK1.7中hash值的右移,异或运算,扩容机制是可以解决链表太长的情况,但还是会出现某个链表过于长的现象,因此加入了红黑树. 在考虑HashMap的插入,查询效率时,因为红黑树的插入,查询也都还可以,所以折中选取了红黑树. 2.扩容机制 先添加元素后进行扩容 数组长度<64时,当链表上的元素>=8时,进行数组扩容(此次扩容方式同JDK1.7); 数组长度>=64时,当链表上的元素>=8时,改成红黑树; 当一棵红黑树上的元素<=6时,改成链表. 3.为什么采用尾插法? 每次插入新元素时,都要进行链表擦长度(红黑树的节点个数)的计算(遍历),无论如何,都要进行遍历,判断是否需要进行链表与红黑树之间的转换,而尾插法就需要遍历,所以采取尾插法.
