HashMap存储结构浅析

àì夳堔傛蜴生んèń 2022-06-12 13:46 156阅读 0赞

**什么是hashcode**  
    分析HashMap之前先介绍下什么Hashcode(散列码)。它是一个int，每个对象都会有一个hashcode，它在内存的存放位置是放在对象的头部（对象头部存放的信息有hashcode，指向Class的引用，和一些有关垃圾回收信息）。具体如何生成hashcode，这个相当复杂，由于我们的主题是“浅析”，所以不深入探讨。有个问题需要讲的是，如果在你的类中覆盖了Object的equals(Object)方法，那么你必须覆盖hashCode方法，不然，当你使用HashMap，HashSet，HashTable时会出现问题。具体原因下文会详细描述。  
**String类的hashcode**  
    String类重写了Object类中的equals和hashCode方法，原因很简单，Object中的equals方法是指比较两个对象是不是指向同一个引用对象，而String类指需要比较内容相不相等就可以了。所以String覆盖了equals方法，同时覆盖了hashCode方法。这里需要提一下Object规范里规定：如果两个对象根据equals(Object)方式是相等的，那么这两个对象的hashCode一定要相等。  
String中的hashcode算法很简单如下：

Java代码   ![收藏代码][icon_star.png]![spinner.gif][]

1.  for (int i = 0; i < len; i++) \{  
2.                  h = 31\*h + val\[off++\];  
3.              \}

for (int i = 0; i < len; i++) {
                    h = 31*h + val[off++];
                }

Val是一个char\[\]，存放的是字符串的各个字符；Len是字符串长度；off从0开始；h从0开始。比如一个字符串“abc”(a的ascii码是97)，它的hashcode算法是：  
h = 31 \* 0 + 97 ==> h = 97;  
h = 31 \* 97 + 98 ==> h = 3105;  
h = 31 \* 3105 + 99 ==> h = 96354;  
所以“abc”的hashCode就是96354  
**存储方式**  
    列表的存储方式是基于数组，如下图：  
![1a9c44da-41a4-368d-8c54-5532a58daa47.jpg][]  
  
    链表的存储方式是基于指针，如下图：（单向链表）  
![7319d809-a000-331f-96da-760f1785ca0e.jpg][]  
  
    HashMap的存储方式是上面两种的结合，如下图：  
![1c28849c-b67c-3461-b48f-54bd4b023b53.jpg][]  
  
**HashMap的存取**  
    HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程：  
    1、 当调用put(key,value)时，首先获取key的hashcode，int hash = key.hashCode();  
    2、 再把hash通过一下运算得到一个int h.  
hash ^= (hash >>> 20) ^ (hash >>> 12);  
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);  
为什么要经过这样的运算呢？这就是HashMap的高明之处。先看个例子，一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。那这样有什么意义呢？看第3步。  
    3、 得到h之后，把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。还有一点需要说明，HashMap的键可以为null，它的值是放在数组的第一个位置。  
    4、 我们用table\[index\]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity，基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity<K,V>对象，在table\[index\]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替换老的value；如果没有，则在table\[index\]插入该Entity，把原来在table\[index\]位置上的Entity赋值给新的Entity的next，这样插入结束。  
再回头看看前面提到的为什么覆盖了equals方法之后一定要覆盖hashCode方法，很简单，比如，String a = new String(“abc”);String b = new String(“abc”);如果不覆盖hashCode的话，那么a和b的hashCode就会不同，把这两个类当做key存到HashMap中的话就会出现问题，就会和key的唯一性相矛盾。  
  
    HashMap取的过程也类似。太累了，不写了。赶紧结束。  
    文中可能会有错误的地方请指出，谢谢！

[icon_star.png]: http://www.iteye.com/images/icon_star.png
[spinner.gif]: /images/20220612/3da448db77ac4a6d9c7dcb8635c73ba9.png
[1a9c44da-41a4-368d-8c54-5532a58daa47.jpg]: /images/20220612/caaeaa1024e44cea8ed1cdc72beca0aa.png
[7319d809-a000-331f-96da-760f1785ca0e.jpg]: /images/20220612/c3101a068ab14f2e8eb8e4ef2b1667c1.png
[1c28849c-b67c-3461-b48f-54bd4b023b53.jpg]: /images/20220612/3af2117a4d3f46d8b40c54ab2fb4ea1d.png