跟我一起阅读Java源代码之HashMap（二）

上一节中实现的SimpleHashMap，没有解决冲突的问题，这一节我们继续深入

由于table的大小是有限的，而key的集合范围是无限大的，所以寄希望于hashcode散落，肯定会出现多个key散落在同一个数组下标下面，

因此我们要引入另外一个概念，将key和value同时存入table[index]中，即将key和value构成一个对象放在table[index]，而且可能存放多个，他们的key对应的index相同，但是key本身不同

 

现在我们就该讨论以什么样的方式存储这些散落在同一个数组下标的元素

可以考虑数组？

也可以考虑链表存储

源码里面是用链表存储的，其实我也没明白这两种方式在这里有什么区别

，感觉无论在检索和存储上都是差不多的效率，

检索都是需要遍历的方式，而存储也可以是顺序的

 

那这个问题留给大家吧。

我们来实现链式存储的方式，首先定义一个链表数据结构Entry：

 

public class Entry<K, V> {
	//存储key
	final K key;
	//存储value
	V value;
	//存储指向下一个节点的指针
	Entry<K, V> next;
	//存储key映射的hash
	final int hash;
}

 

新的EntryHashMap实现方式

 

public class EntryHashMap<K, V> {

	transient Entry[] table;

	transient int size;

	public EntryHashMap() {
		table = new Entry[10];
	}

	public V put(K key, V value) {
		// 计算出新的hash
		int hash = hash(key.hashCode());
		// 计算出数组小标i
		int i = indexFor(hash, table.length);
		// 遍历table[i]，如果table[i]没有与新加入的key相等的，则新加入
		// 一个value到table[i]中的entry，否则将新的value覆盖旧的value并返回旧的value
		for (Entry<K, V> e = table[i]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
				V oldValue = e.value;
				e.value = value;
				return oldValue;
			}
		}
		addEntry(hash, key, value, i);
		return null;
	}

	public V get(K key) {
		// 计算出新的hash
		int hash = hash(key.hashCode());
		// 计算出数组小标i
		int i = indexFor(hash, table.length);
		for (Entry<K, V> e = table[i]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
				return e.value;
			}
		}
		return null;
	}

	private void addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K, V> e = table[bucketIndex];
		// 将新的元素插入链表前端
		table[bucketIndex] = new Entry<>(hash, key, value, e);
		size++;
	}

	/**
	 * 通过hash code 和table的length得到对应的数组下标
	 * 
	 * @param h
	 * @param length
	 * @return
	 */
	static int indexFor(int h, int length) {
		return h & (length - 1);
	}

	/**
	 * 通过一定算法计算出新的hash值
	 * 
	 * @param h
	 * @return
	 */
	static int hash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}
	
}

 

测试

public static void main(String[] args) {
		EntryHashMap<String, String> hashMap = new EntryHashMap<String, String>();
		hashMap.put("key", "value");
		System.out.println(hashMap.get("key"));
}

 

请阅读系列文章 

 

跟我一起阅读Java源代码之HashMap（三）

 

 

 

 

 

我昨天继续看了下源码，发现remove操作的时候，链表确实效率高，还有你说的那个重新散列，那链表的优势就更大了，你的回答我非常受益，谢谢

 

恩，是的，链表的特点就是适合inset/delete operation, 数组就不适应了

个人认为链表比数组还有一点优势：
数组需要申请一个较大的连续内存空间，而链表可以申请离散的内存空间，对于内存存储要求更加合理一点

对于内存这点，我觉得各有各的优势，连续的内存可以提高运算的性能，在内存足够用的情况下，为什么不呢？