HashMap原理

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

从上图我们可以发现哈希表是由数组+链表组成的，在一个长度为16的数组中，每个元素存储在链表的一个结点中，这些元素的具体存储位置通常是按照hash(key)^(length-1)来获得。例如91^15=11,155^15=11,171^15=11,所以91、155、171都存储在数组下标为11的位置。

Java中的HashMap

首先是哈希的插入，我们可以看JDK1.6中HashMap插入方法的源代码：

public V put(K key, V value) {
		// 如果key为null，调用putForNullKey方法进行处理
		if (key == null)
			return putForNullKey(value);
		// 对key进行再一次的hash运算
		int hash = hash(key.hashCode());
		// 根据hash值和table长度计算应该存放的位置
		int i = indexFor(hash, table.length);
		// 当该下标已有数据时
		for (Entry<K, V> e = table[i]; e != null; e = e.next) {
			Object k;
			// 如果key的hash值相同并且key也相同，则进行替换
			if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
				V oldValue = e.value;
				e.value = value;
				e.recordAccess(this);
				// 返回该key的原值
				return oldValue;
			}
		}
		modCount++;
		// 添加新的Entry
		addEntry(hash, key, value, i);
		return null;
	}

代码中用到实现了Map.Entry接口的内部类Entry<K, V>，其实就是一个key-value对，里面有四个属性，分别为key、value、hash、next。

每当插入键值对为添加一个新的Entry时，会检查是否需要扩容

	void addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K, V> e = table[bucketIndex];
		table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
		//检查有没有超过扩容阀值，超过则扩容
		if (size++ >= threshold)
			resize(2 * table.length);
	}

 扩容后链表数组长度的最大值为Integer的最大值

void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		//链表数组最大值为Integer.MAX_VALUE
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry[] newTable = new Entry[newCapacity];
		//rehash操作
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

  重构链表数组的具体操作如下

void transfer(Entry[] newTable) {
		Entry[] src = table;
		int newCapacity = newTable.length;
		for (int j = 0; j < src.length; j++) {
			Entry<K, V> e = src[j];
			//检查下标为j的数组是否存在链表
			if (e != null) {
				src[j] = null;
				do {
					Entry<K, V> next = e.next;
					int i = indexFor(e.hash, newCapacity);
					e.next = newTable[i];
					//将链表当前结点的元素放在新数组中
					newTable[i] = e;
					//处理下一个结点
					e = next;
				} while (e != null);
			}
		}
	}

可能不少人会有这么个疑问：要是一次性往一个HashMap中插入上千乃至上万个键值对的，那不是需要进行多次哈希表的重构，岂不是很浪费性能？
Java中用Map map = new HashMap()初始化一个HashMap的时候，默认的数组长度为16，实际上当HashMap中的键值对超过16*0.75=12个时，就会扩容。

//默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
//默认装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表数组
transient Entry[] table;
//键值对的数量
transient int size;
//扩容阀值
int threshold;
//装载因子
final float loadFactor;

	public HashMap() {
		this.loadFactor = DEFAULT_LOAD_FACTOR;
		threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
		table = new Entry[DEFAULT_INITIAL_CAPACITY];
		init();
	}

  同时Java也提供了一个可以指定容量大小和装载因子的初始化方法，Map map = new HashMap(10000,0.8f);不过用此方法初始化出的HashMap容量不是10000，而是8192

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);
		// Find a power of 2 >= initialCapacity
		int capacity = 1;
		//链表数组的大小为2的n次方，便于取余后确定key所在的数组下标
		while (capacity < initialCapacity)
			capacity <<= 1;
		this.loadFactor = loadFactor;
		//阀值为容量*装载因子
		threshold = (int) (capacity * loadFactor);
		//实例出一个该容量的Entry数组
		table = new Entry[capacity];
		init();
	}