跟我一起阅读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相同呢，这样的情况是存在的，如何解决？

请看系列文章二

?