hashmap解析

1.hashmap
1)hashmap用过么，说说具体用途
答：用过，在平常工作中经常用到hashmap这种数据结构，hashmap是基于 map接口实现的一种键值对<key,value>的存储结构，允许null值，同时非有序，非同步（即线程不安全）hashmap底层实现是数组+链表+红黑树（jdk1.8增加了红黑树部分。）它存储和查找数据时，是根据键key的hashcode的值计算出具体的存储位置，hashmap最多只允许一条记录的键key为null，hashmap增删改查等常规操作都有不错的执行效率，是arraylist和linkedlist等数据结构的一种折中实现。

2.说说hashmap常用操作的底层实现原理？如存储put（key，v value），查找get（object key），删除（object key ），修改replace（key，v value）等操作
答：调用put（K key，V value）操作添加一个key-value键值对时，进行了如下操作：判断哈希表Node<K,V>[]table是否为空或者为null，是则执行resize（）方法进行扩容。
根据插入的key的hash值，通过（n-1）&hash当前元素的hash值&hash表长度-1（实际就是hash值%hash表长度）计算出存储位置table[i]。如果存储位置没有元素存放，则将新增节点存储在此位置table[i]。
如果存储位置已经有键值对元素存在，则判断该位置元素的hash值和key值是否和当前操作元素一致，一致则证明是修改value操作，覆盖value即可。
当前存储位置即有元素，又不和当前操作元素一致，则证明此处位置table[i]已经发生了hash冲突，则通过判断头节点是否是treeNode,如果是treeNode则证明此位置的结构是红黑树，以红黑树的方式新增节点。
如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置，随后判断当前链表长度是否大于等于8，是则当前存储位置的链表转化为红黑树。遍历过程中如果发现key已经存在，则直接覆盖value。
插入成功后，判断当前存储键值对的数量大于阈值threshold是则扩容。

调用get（Object key）操作根据键key查找对应的key-value键值对时，进行了如下操作：
先调用hash（key）方法计算出key的hash值
根据查找的键值key的hash值，通过（n-1）&hash当前元素的hash值&hash表长度-1（实际就是hash值%hash表长度）计算出存储位置table[i],判断存储位置是否有元素存在。
如果存储位置有元素存放，则首先比较头结点元素，如果头结点的key的hash值和要获取的key的hash值相等，并且头结点的key本身和要获取的key相等，则返回该位置的头结点。
如果存储位置没有元素存放，则返回null。
如果存储位置有元素存放，但是头结点元素不是要查找的元素，则需要便利该位置进行查找。
先判断头结点是否是treeNode，如果是treeNode则证明此位置的结构是红黑树，以红黑树的方式遍历查找该结点，没有则返回null。
如果不是红黑树，则证明是单链表。遍历单链表，逐一比较链表结点，链表结点的key的hash值和要获取的key的hash值相等，并且链表结点的key本身和要获取的key相等，则返回该结点，遍历结束仍未找到对应的key的结点，则返回null。

调用remove（Obkect key）的操作根据key删除对应的key-value键值对时，进行了如下操作：
先调用hash（key）方法计算出key的hash值
根据查找的键值key的hash值，通过（n-1）&hash当前元素的hash值&hash表长度-1（实际就是hash值%hash表长度）计算出存储位置table[i]，判断存储位置是否有元素存在。
如果存储位置有元素存放，则首先比较头结点元素，如果头结点的key的hash值和要获取的key的hash值相等，并且头结点的key本身和要获取的key相等，则该位置的头结点即为要删除的结点，记录此结点至变量node中。
如果存储位置没有元素存放，则没有找到对应要删除的结点，则返回null。
如果存储位置有元素存放，但是头结点元素不是要删除的元素，则需要遍历该位置进行查找。
先判断头结点是否是treeNode,如果时treeNode则证明此位置的结构是红黑树，以红黑树的方式遍历查找并删除该结点，没有则返回null。
如果不是红黑树，则证明是单链表。遍历单链表，逐一比较链表结点，链表结点的key和hash值和要获取的key的hash值相等，并且链表结点的key本身和要获取的key相等，则此为要删除的结点，记录此结点至变量node中，遍历结束仍未找到对应key的结点，则返回null。如果找到要删除的结点node，则判断是否需要比较value也是否一致，如果value值一致或者不需要比较value值，则执行删除结点操作，删除操作根据不同的情况与结构进行不同的处理。
如果当前结点是树结点，则证明当前位置的链表已变成红黑树结构，通过红黑树结点的方式删除对应结点。
如果不是红黑树，则证明是单链表。如果要删除的是头结点，则当前存储位置table[i]的头结点指向删除结点的下一个结点。
如果要删除的结点不是头结点，则将要删除的结点的后继结点node.next赋值给要删除结点的前驱结点的next域，即p.next=node.next;。

调用replace（K key,V value）操作根据键key查找对应的key-value键值对，随后替换对应的值value，进行了如下操作：
先调用hash（key）方法计算出key的hash值 随后调用getNode方法获取对应key所映射的value值。记录元素旧值，将新值赋值给元素，返回元素旧值，如果没有找到元素，则返回null。

hash冲突（hash碰撞）是什么？为什么会出现这种现象？如何解决hash冲突？
答：hash冲突：当我们调用put（K key，V value）的、操作添加key-value键值对，这个key-value键值对存放在的位置是通过扰动函数（key==null）？0:（h=key.hashCode()）^(h>>>16)计算键key的hash值，随后将这个hash值%模上哈希表Node<K,V>[ ]table的长度得到具体的存放位置。所以put（K key，V value）多个元素，是有可能计算出相同的存放位置。此现象就是hash冲突或者hash碰撞。
hash冲突解决：开发定址法 ，在散列法，链地址法，公共溢出区法