【Java】详解HashMap原理

HashMap介绍

Map是一种存放键值对的数据类型。在Java中，最为常用的三个基于hashing原理实现的类是：HashMap、HashTable、HashSet。（实线段表示泛化关系，即继承，实线是实现关系）

HashMap的特点

HashMap中Key值不可以相同，但是value值可以相同。HashMap可以使用null作为key值，但需要规避这样的做法。HashMap无法确保线程同步，通常在多线程情况下会使用ConcurrentHashMap或者Collections.synchronizedMap()来获取一个线程安全的Map对象。HashMap的映射没有顺序，而且也不能保证顺序永远不。HashMap的初始容量是2^4，即16，填充因子默认为0.75。HashMap计算Hash的方法是对key的hashCode()值进行二次哈希。 HashMap存取速度快，可以将Entry作为键值。如:Map(String,HashMap<String,HashMap<String,String>()>())。

HashMap原理

HashMap中，我们通常所存入的一组键值对为Entry,把存放Entry的容器称为bucket，即桶。

存放过程:put(key,value)利用hashCode(）方法计算key的Hash值，将这个Hash值对应到桶的下标，存入Entry。如果这个位置上有Entry,则在这个位置上以链表的形式存储Entry，新进来的Entry在链头。取值过程:get(key)，根据key的hashCode(）值找出该Entry在bucket中的位置，取出该Entry，再取出对应的value值即可。 这个过程需要注意，如果产生Entry链了会大大影响HashMap的性能。 HashMap默认初始容量为16(1<<4)，最大容量为1073741824(1<<30)。默认的填充因子是0.75。 之所以规定这些常量，一是为了节省内存空间，二是为了扩展HashMap的容量。HashMap的容量随着存入而改变，每次都是原容量的2倍。这一过程大致可以理解为： 当使用默认初始容量的情况下，存储到达16*0.75=12时，HashMap的存储容量会立马变成32。 此时，存储到达32*0.75=24时，HashMap的存储容量会立马变成64，以此类推。

使用构造方法可以改变默认初始容量和填充因子，如下：

//默认构造方法 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } //可改变默认初始容量的构造方法 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //可改变默认初始容量和填充因子的构造方法 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }