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

最近闲的很，想和大家一起学习并讨论下Java的一些源代码以及其实现的数据结构，

不是什么高水平的东西，有兴趣的随便看看

 

1. 为什么要用Map，以HashMap为例

    很多时候我们有这样的需求，我们需要将数据成键值对的方式存储起来，根据key来获取value(value可以是简单值，也可以是自定义对象)

    当然用对象数组也能实现这个目的，查找时可以遍历数组，比较关键字来获取对应的value

    从性能上来讲，遍历大数组会消耗性能

    从API易用性来讲，需要自己实现查找的逻辑

    所以用HashMap是必要的    

 

2. HashMap的数据结构是怎么样的

 

    我一直对HashMap的内部结构很好奇，看了源码之后发现他是用散列实现的，即基于hashcode

    大体思想是这样的

    1. 首先建立一个数组用来存取数据，假设我们定义一个Object[] table用来存取map的value

这个很容易理解，key存在哪里呢？暂时我不想存储key

    2. 获得key的hashcode经过一定算法转成一个整数

        index，这个index的取值范围必须是0=<index<table.length，然后我将其作为数组元素的下标

        比如执行这样的操作：table[index] = value;

        这样存储的问题解决了

    3. 如何通过key去获取这个value呢

        这个太简单了，首先获取key的hashcode，然后通过刚才一样的算法得出元素下标index

        然后value = table[index]

 

简单的HashTable实现如下

 

public class SimpleHashMap {

	private Object[] table;

	public SimpleHashMap() {
		table = new Object[10];
	}

	public Object get(Object key) {
		int index = indexFor(hash(key.hashCode()), 10);
		return table[index];
	}

	public void put(Object key, Object value) {
		int index = indexFor(hash(key.hashCode()), 10);
		table[index] = value;
	}

	/**
	 * 通过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){
		SimpleHashMap hashMap = new SimpleHashMap();
		hashMap.put("key", "value");
		System.out.println(hashMap.get("key"));
	}
}

 

这个简单的例子大概描述了散列实现hashmap的过程

但是还很不成熟，我发现至少存在以下两个问题

1. hashmap的size是固定的

2. 如果不同的key通过hashcode得出的index相同呢，这样的情况是存在的，如何解决？

请看系列文章二