kurenai
做JAVA开发的程序员们，每天都在用hashMap，可是你真的了解hashMap吗？
hashMap作为一个key-value形式的数据结构，以键值对的方式存储数据，下面以链地址法为例，简单来说就是通过计算key的hashCode然后使用equals方法进行比较，把相同hashcode值的数放在一个桶里(其实就是一个数组)，在一个数组中的元素又怎么存储呢？通过单向链表，一个接一个的接起来！
这是链地址法hashMap的图示:
再来看个概念，大O表示法:一定量的运算所需要的时间级别！比如一串无序的数据量为N的数据，通过顺序查找的方式查找某个数，找到的这个数所需要的比较次数评论为N/2，我们就用O(N)来表示查找时间为线性级别的！如果是一个数组，假设数量为500，那么查找某个数的比较次数就一定不超过500，这样就使用O(1)来表示这个查找是常量级的查找！
hash函数的定义往往是为了获得更为平均的hashcode，让key对应的value能平均分配在不同的桶里，为什么平均分配是最好的？我们用极限理论来举个栗子:
假设有数量为250000(1-250000)的数据，如果按照500来取模作为hash函数，余数为0-499的分别放在不同的500个桶里(数组)，需要查找某个数的时候，只需要先计算余数获得数组下标(O(N))，再从这个数组元素(链表)中取出这个数即可(O(N))，就是250+250＝500次就能得到这个数，但是如果这250000个数的值都是250000，也就是说数组下标为1-499(当然这时候已经不存在了)的数组元素中都是空的，而下标为0(数组第一个元素)的链表个数为250000，这时候查找某个数的比较次数平均为125000，性能下降为O(N)，从O(1)-->O(N)差别很大很大！
总之，hashMap中的hash算法是为了尽量让key分配在不同的桶里，减少冲突的产生，如果能让数据平均分配到桶里，那么hashMap的查询将得到最大化的提升！
在JAVA8中，hashMap对于冲突问题，有了极大的性能提升，如果出现的冲突达到某个阈值(源码中使用TREEIFY_THRESHOLD表示)，会把原来的链表结构动态的变为红黑树进行存储，把O(N)级别的的查找变为O(logn)，性能提升不要太多。。
下面是JAVA8hashMap的图示:
从源码中获取到算法和数据结构的使用，才能真正对自己掌握底层技术，和优化性能有直接作用，文中提到的红黑树为什么查找快，改天会进行分享，更多的技术分享，敬请关注。。
谢逅架构
HashMap的hash函数需要衡量两方面：降低hash冲突和尽量减少hash计算性能消耗。
HashMap插入数据时会先计算KEY的hash值，然后根据这个hash值确定数据在table中的下标。计算方法如下，用table的长度减1后与hash值进行位运算与操作，由于hashmap的长度一般不大，所以hash值参与计算的都是后面几位，容易造成冲突。
为了减少这种冲突，HashMap的hash函数，将KEY的hashcode前16位和后16位进行异或计算，这样会有效的降低冲突机率，同时运算量也非常小。代码如下
希望能解答题主的疑惑。
