深入Java集合学习系列(一)

HashMap的实现原理

1. HashMap概述：

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

2. HashMap的数据结构：

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

   源码如下：

Java代码 

1. /** 
2. * The table, resized as necessary. Length MUST Always be a power of two. 
3. */  
4. transient Entry[] table;  
6. static class Entry<K,V> implements Map.Entry<K,V> {  
7. final K key;  
8. V value;  
9. Entry<K,V> next;  
10. final int hash;  
11. ……  
12. } 

可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。

本教程由尚硅谷教育大数据研究院出品，如需转载请注明来源，欢迎大家关注尚硅谷公众号（atguigu）了解更多。