4.HashMap

/**

* 每天一个知识点day04  TODO HashMap(一)

*

* 1.初始大小capacity16，(必须是2的次幂), 哈希表的最大长度 1<<30 ,默认加载因子 0.75。

* 2.JDK1.7中，组成为数组+链表。JDK1.8后为数组+链表+红黑树。

*

* HashMap与HashTable的区别？

* 1.HashMap允许存入null键 null值，是线程不安全的，如果存入相同的键则会覆盖。

* 2.HashTable 不允许存入null键null值。在方法上用synchronized修饰，是线程安全的。

* 3.HashMap继承自AbstractMap类，HashTable继承自Dictionary类。

* 4.HashMap默认容量为16，扩容时每次扩容原始容量的两倍，HashTable默认容量为11，每次扩容原容量*2+1

* 5.添加key-value的hash算法不同，HashMap添加是使用自定义hash算法

* (对key进行hashCode()操作并与高16位做异或运算)

* 而HashTable直接采用key的hashCode();

*

* 底层原理？

* 通过put和get来存储和获取对象，put方法传递键值时，先对key做一个hashCode的计算来得到他在bucket数组中的

* 位置来存储Entry对象。获取对象时，通过get获取到bucket的位置，

* 再通过键对象的equals()方法来找到正确的键值对，返回值对象。

*

* put方法是如何实现的？

* 1.计算关于key的hashCode(与key.hashCode的高16位做亦或运算)

* 2.如果散列表为null时，调用resize()初始化散列表。

* 3.如果没有发生碰撞，直接添加元素到散列表中去。

* 4.如果发生了碰撞（hashCode值相同），进行三种判断。

*  若key地址相同或equals后内容相同，则替换旧值。

*  如果是红黑树结构，就调用树的插入方法。

*  链表结构，则循环遍历整个链表，直到某个结点为空，尾插法进行插入。插入之后判断链表个数是

*  否到达变成红黑树的阈值8。

* 5.如果bucket满了大于阈值，则resize进行扩容。

*

* 扩容？

* 概括来讲，扩容需要重新分配一个新数组，是老数组的两倍长，然后遍历整个老结构，把所有元素挨个重新hash分配到新结构中去。

*

* get方法是如何实现的？

* 对key的hashCode进行hash(),&运算计算下标获取bucket位置，如果在桶的首位上就可以直接返回，否则在树中找或者

* 在链表中查找，如果有hash冲突，则利用equals方法去遍历链表查找节点。

*

* 为什么不直接将key作为哈希值，而是异或高16位？

* 增加随机性，减少哈希碰撞。

*

* 传统HashMap的缺点（为什么引入红黑树）？

* JDK1.8版本以前，HashMap实现是数组+链表，即使哈希函数取得再好，也很难达到百分百均匀分布，当HashMap中有

* 大量元素都放在同一个桶时，这个桶下有一条长长的链表，这个时候HashMap相当于一个单链表，加入单链表有n个元素

* 遍历的时间复杂度是O(n)，完全失去了优势。引入红黑树后时间复杂度变为O(logn)

*

* 什么类型的元素作为key？

* Integer String这种不可变类型，像对String的一切操作都是新建一个String对象，不可变类天生是线程安全的。

*

*/