最近闲的很,想和大家一起学习并讨论下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相同呢,这样的情况是存在的,如何解决?