Java岗大厂面试百日冲刺 - 日积月累，每日三题【Day12】—— 集合框架2（HashMap）
public native int hashCode();
native 的意思就是通知操作系统，这个函数你必须给我实现，因为我要使用。所以native关键字的函数都是操作系统实现的， java只能调用。
java是跨平台的语言，既然是跨了平台，所付出的代价就是牺牲一些对底层的控制，而java要实现对底层的控制，就需要一些其他语言的帮助，这个就是native的作用了
staticfinalintspread(int h){return(h^(h>>>16))& HASH_BITS;}7fffffff是8位16进制
每个16进制代表4个bit
8✖4bit=32bit=4Byte
f的二进制为：1111，7的二进制位0111
int类型的长度位4Byte
左边起，第一位为符号位，0代表正数，1代表负数
0x7fffffff代表int的最大值
bit 就是1位二进制数，比如 1 或者 0；1Byte 就是 1 个字节
1 个字节是由 8 个二进制位组成的。比如1111111,00000000等。
LinkedHashMap
HashMap是无序的，HashMap在put的时候是根据key的`hashcode`进行hash然后放入对应的地方。所以在按照一定顺序put进HashMap中，然后遍历出HashMap的顺序跟put的顺序不同。单纯的HashMap是无法实现排序的。区别：
1.HashMap里面存入的键值对在取出的时候是随机的,也是我们最常用的一个Map.它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。
2.TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
- LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现.
LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。
/**
* The head (eldest) of the doubly linked list.
*/transientLinkedHashMap.Entry<K,V> head;/**
* The tail (youngest) of the doubly linked list.
*/transientLinkedHashMap.Entry<K,V> tail;//将加入的p节点添加到链表末尾privatevoidlinkNodeLast(LinkedHashMap.Entry<K,V> p){LinkedHashMap.Entry<K,V> last= tail;
tail= p;if(last==null)
head= p;else{
p.before= last;
last.after= p;}}//LinkedHashMap的节点类staticclassEntry<K,V>extendsHashMap.Node<K,V>{Entry<K,V> before, after;Entry(int hash,K key,V value,Node<K,V> next){super(hash, key, value, next);}}JAVA在JDK1.4以后提供了LinkedHashMap来帮助我们实现了有序的HashMap！
LinkedHashMap取键值对时，是按照你放入的顺序来取的。
TreeMap怎么实现有序的
TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。TreeMap实现了SortedMap接口，它是一个key有序的Map类。
要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。
TreeMap<String,String> map=newTreeMap<String,String>(newComparator<String>(){@Overridepublicintcompare(String o1,String o2){return o2.compareTo(o1);}});1.8 引入红黑树
主要是为了提升在 hash 冲突严重时（链表过长）的查找性能，使用链表的查找性能是 O(n)，
而使用红黑树是 O(logn)。
触发链表节点转红黑树节点（treeifyBin）；
- 当同一个索引位置的节点在新增后达到9个（阈值8）
- 如果此时数组长度大于等于 64，而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。
移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。
链表红黑树如何互相转换？阈值多少？
链表转红黑树的阈值为：8 红黑树转链表的阈值为：6 经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，从概率上讲，阈值为8足够用；至于为什么红黑树转回来链表的条件阈值是6而不是7或9？因为如果hash碰撞次数在8附近徘徊，可能会频繁发生链表和红黑树的互相转化操作，为了预防这种情况的发生。HashMap是线程安全的吗？
正经回答： 不是线程安全的，在多线程环境下，JDK1.7：会产生死循环、数据丢失、数据覆盖的问题；
JDK1.8：中会有数据覆盖的问题。以1.8为例，当A线程判断index位置为空后正好挂起，B线程开始往index位置写入数据时，这时A线程恢复，执行写入操作，这样A或B数据就被覆盖了。
hashmap的容量是2^n
2^n好处
①效率高
②索引值在容量中，不会超出数组长度（(n - 1) 和 hash 做与运算）
例如：
当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1，
例如 00001111 & 10000011 = 00000011
重点：2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
- initialCapacity 不为 2次幂时，HashMap方法做了处理，能保证n永远都是2次幂。
- ①获取数据通过hash，所以，读方法和写方法都和hash相关，②初始容量默认16，③hash也做了特别处理，得到hashcode值h，会右移15位做位或运算，使高16位也尽量参与到hash的运算，减少冲突。
举例：
①HashMap的容量为16转化成二进制为10000，length-1得出的二进制为01111
哈希值为1111 ，可以得出索引的位置为15
②HashMap的容量为15转化成二进制为1111，length-1得出的二进制为1110
哈希值为1111和1110
那么两个索引的位置都是14，就分布不均匀了。
按位与
- 符号：&
- 真值表：1&0=0、1&1=1、0&0=0、0&1=0
- 位与时两个操作数是按照二进制位彼次对应位相与的，逻辑与是两个操作数作为整体来相与的。
按位或
- 符号：|
- 1|0=1、1|1=1、0|0=0、0|1=1
- 位或时两个操作数是按照二进制位彼次对应位相与的，逻辑或是两个操作数作为整体来相或的。