扫码加入数据分析学习群

HashMap 采用一种算法决定每个元素的存储位置。当执行map.put(String,Obect)方法时，系统将调用String的hashCode()方法得到其hashCode值——每个Java对象都有hashCode()方法，都可通过该方法获得它的hashCode值。得到这个对象的hashCode值之后，系统会根据该hashCode值来决定该元素的存储位置。源码中用到了一个重要的内部接口：Map.Entry，每个Map.Entry其实就是一个key-value对。从上面程序中可以看出：当系统决定存HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。

Hashmap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表。

HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素，但是出现单链表后，单个bucket里存储的不是一个Entry，而是一个Entry链，系统只能必须按顺序遍历每个Entry，直到找到想搜索的Entry为止——如果恰好要搜索的Entry位于该Entry链的最末端（该Entry是最早放入该bucket中），那系统必须循环到最后才能找到该元素。