怎么理解hash原理？以hashmap为例？

Question

java中hashmap的工作原理是什么呢？

Answer 1

JDK1.8之前采用数组+链表的形式存储数据、JDK1.8之后当阀值达到 [8] 时，数据结构采用数组+红黑树

Answer 2

hash是为了尽量使每个不同的任意东西可以用同一种算法来表示他们不同。因为这是一个算法所以有可能不同的东西算出来的值是一样的。
比如设计个算法苹果算出来是1，香蕉算出来是2，梨子算出来是3，但是有可能你算航空母舰的时候也算出1来了。所以不同的东西用相同的逻辑算法算出的值有可能一样。也就是说hash值相同的对象可能不一样。再来说map，map里面有个Node类型数组，每个对象添加的时候会根据他的hash值来计算出他应该放在数组的哪个位置。而这个node的结构是这样的他里面含有一个Object类型的value用来存放你添加的对象，同时有个next用来指向下一个node。为啥要指向下一个，因为相同的hash值会被放在同样的数组位置，但是hash值相同可能表示不同的对象，所以要判断如果条件的对象和已经在数组那个位置上的对象相同。那么就不添加这个元素，如果不同那么久添加，并且被next为null的这个node节点的value引用。基本原理就是这样。删除，获取自己动脑想吧，差不多的。因为同一个位置可能存在多个不同的对象，所以要用链表或者红黑树来存储，当然你要是自己实现，你想用数组想用队列想用栈同样可以实现，只不过是效率不高罢了

Answer 3

感谢大神，但是有个疑问，添加时，根据hash算法算出位置时，如果hashcode值相同是不是会覆盖？

Answer 4

不会覆盖，还是那个位置，只不过那个数组的格子里面存了一个链表，真正的数据是放在链表结构里，如果有重复的hash值而对象又不一样的话，那么他就放在链表里面，也就是说有一万个不一样的东西，但是他们的hash值是一样的，那么他们都要放在数组的同一个位置，但是那个位置里存放了一个链表头，其他的元素就排队放在链表里，当然一万太夸张了，我说的这个意思你能明白就行。在不超过hashmap的初始容量的四分之三情况下不会更改元素的位置，超过了的话hashmap会扩容，这时候里面的元素就要重新选位置了。

Answer 5

我有种算法，能在hashmap每次扩容后，新元素优先存入数组空位置，而不用每次扩容后都必须rehash的毛病。

Answer 6

hashcode相同,元素会落在相同的桶中,之后会进行一次比较,所以,hashMap的key都尽可能的实现Comparable接口(参见HashMap的putVal方法实现),也会用 == 比较引用是否相同,不同则置于链表末端(如果是树形化的桶另当别论)
HashMap的中的hash方法对hashCode进行了二次运算,高16位和低16位做异或运算,避免因为hashCode的低位相同而一直落在同一个桶中,
所以HashMap的各个链表大部分时间才都是单节点的.参考 https://blog.csdn.net/ZTzhubajie/article/details/86693946