[转帖]跟我一起阅读Java源代码之HashMap（一）_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛

总帖数

每页帖数

1/1页

返回列表

发起投票

查看: 3508 | 回复: 0

主题： [转帖]跟我一起阅读Java源代码之HashMap（一）

jxxs_12

注册用户

等级：下士
经验：190
发帖：14
精华：0
注册：2013-1-15
状态：离线
发送短消息息给jxxs_12

加好友发送短消息息给jxxs_12

发消息

发表于：

2013-1-15 14:30:06 | [全部帖] [楼主帖]

楼主

最近闲的很，想和大家一起学习并讨论下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实现如下

Java代码

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"));
}
}

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