MyException - 我的异常网
当前位置:我的异常网» 编程 » HashMap源码解读(1)

HashMap源码解读(1)

www.MyException.Cn  网友分享于:2013-08-27  浏览:9次
HashMap源码解读(一)
HashMap源码解读(一)


1、HashMap的存储结构
2、HashMap的初始化
3、元素Hash值获取及通过hash值找到talbe下标索引
4、元素添加方法addEntry
5、HashMap扩容
6、老table重新hash成新table
7、key为null,存到哪去了
8、查找元素get(Object key)
9、根据key删除元素


1、HashMap的存储结构

  在HashMap的Field中有:

transient Entry[] table;

  而Entry的定义如下:
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
 .........
}

简单说就是一个数组+链表,结构如下图:




2、HashMap的初始化
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}


    构造方法中出现的几个关键字段:loadFactor ,threshold,CAPACITY,table
其中table上面讲了,是HashMap的存储结构。CAPACITY这个是构建HashMap的时候的容量,这里使用了系统默认的初始容量,loadFactor 是加载因子,用处是和CAPACITY相乘获得threshold,这个文档的说明如下:The next size value at which to resize (capacity * load factor)。其实就是HashMap扩容的临界值,超过这个值,则重新扩容。
    这样就说明了loadFactor 的用处了。这里有人要问了。为什么要这个东西。这里就涉及到HashMap的原理了。HashMap中存储元素的时候,首先得先通过其自己的hash算法找到存储在talbe数组的索引值。但是这个hash算法并不能保证,每一个元素对应不同的talbe数组的索引值,当放入HashMap的元素过多的时候,就容易出现相同的索引值,在算法里叫冲突,这时候元素就会被加到该索引值下的链表当中,这样查找的效率就会大大降低,这显然违背了HashMap快速查找的初衷了。所有HashMap在设计的时候,就是用了这样一个加载因子,如果存储的元素个数占table长度的比例大于loadFactor 加载因子的时候,冲突加剧,这样我们就得扩容解决这样的问题。
    所以总结影响HashMap效率的两个因素:1.初始容量 2.加载因子。解决的本质无非就是减少hash冲突。

3、元素Hash值获取及通过hash值找到talbe下标索引
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
	return h ^ (h >>> 7) ^ (h >>> 4);
}

    这个不深究,结果是获得一个随机点的hash值
static int indexFor(int h, int length) {
	return h & (length-1);
}

    这个就是获得元素对应table下标索引的方法,h是通过上面的hash(int h)方法获得,length是table的长度

4、元素添加方法addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
	table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
	if (size++ >= threshold)
		resize(2 * table.length);
}
//Entry的构造方法
Entry(int h, K k, V v, Entry<K,V> n) {
	value = v;
	next = n;
	key = k;
	hash = h;
}


    addEntry方法里出现的几个参数分别是:hash-->元素key的hash值,key,value不用说了,bucketIndex是计算出来的该元素对应的table下标索引。方法的前两句是,根据传入的参数生成一个Entry元素,他的next为现有table[bucketIndex]。
    说白了就是将新元素加到该元素对应table[bucketIndex]链表的表头。流程如下图:


5、HashMap扩容
void resize(int newCapacity) {
	Entry[] oldTable = table;
	int oldCapacity = oldTable.length;
	if (oldCapacity == MAXIMUM_CAPACITY) {
		threshold = Integer.MAX_VALUE;
		return;
	}
	Entry[] newTable = new Entry[newCapacity];
	transfer(newTable);
	table = newTable;
	threshold = (int)(newCapacity * loadFactor);
}


在元素添加方法addEntry中,添加完元素后,有下面两行代码:

if (size++ >= threshold)
	resize(2 * table.length);


    size表示的是HashMap中有多少个元素,当元素的个数超过临界值时,会自动调用扩容方法,可以看出HashMap的扩容是翻番的扩2 * table.length。我们在来看看resize扩容方法。
    前面几行是判断扩容后是否好过了最大的int值。后面几行是将原来的table中的元素,重新hash放到新的扩容后的table中。可能大家对transfer(newTable)这个方法很困惑。接下来,我们来解读这个方法的实现。

6、老table重新hash成新table
void transfer(Entry[] newTable) {
	Entry[] src = table;
	int newCapacity = newTable.length;
	for (int j = 0; j < src.length; j++) {
		Entry<K,V> e = src[j];
		if (e != null) {
			src[j] = null;
			do {
				Entry<K,V> next = e.next;
				int i = indexFor(e.hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			} while (e != null);
		}
	}
}


    这个方法的主要作用就是,将老的table中的所有不为空的元素,重新hash放到新的table中去。估计在do之前的大家能很好理解。就是遍历table中不为空的元素。这时候找出来的e = src[j]是一个Entry链表。所以,如果不为空,还要遍历这个链表中的每一个元素,并将这些元素重新hash到新table中。下面我们对于代码讲解。
//将第一个元素e后的链表截取出来
Entry<K,V> next = e.next;
//找到e对应新table的下标索引
int i = indexFor(e.hash, newCapacity);
//将e插入到新table下标索引链表的表头
e.next = newTable[i];
//将该新table下标索引重新定位为e,这样就完成了一个元素的重新hash
newTable[i] = e;
//将截取的剩余的链表继续hash
e = next;
示意图如下:
1、Entry<K,V> next = e.next;

2、e.next = newTable[i];

    即这里的e就是Entry[j],也就是

3、newTable[i] = e;
    因为newTable[i]本身是一个指向浅蓝色Entry[i]的引用,这个时候,我们在将这个引用指向红色Entry[j],这样就完成了老table中一个元素的重新hash到新table中。


7、key为null,存到哪去了
    在put方法里头,其实第一行就处理了key=null的情况。
if (key == null)
	return putForNullKey(value);
//那就看看这个putForNullKey是怎么处理的吧。
private V putForNullKey(V value) {
	for (Entry<K,V> e = table[0]; e != null; e = e.next) {
		if (e.key == null) {
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;
		}
	}
	modCount++;
	addEntry(0, null, value, 0);
	return null;
}

    可以看到,前面那个for循环,是在talbe[0]链表中查找key为null的元素,如果找到,则将value重新赋值给这个元素的value,并返回原来的value。
    如果上面for循环没找到。则将这个元素添加到talbe[0]链表的表头。

8、查找元素get(Object key)
public V get(Object key) {
	if (key == null)
    	return getForNullKey();
	int hash = hash(key.hashCode());
	for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
		Object k;
		if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
		return e.value;
	}
	return null;
}

    前面两行是找key为null的元素,前面说过,key为null的元素,是放在table[0]这个链表的。所以要找的话,直接到table[0]中查找就行了。
    如果没找到的话。则根据key的hash值找到元素所在table中下标索引,根据其在找到元素所在链表,在遍历链表,找到该元素并返回其value,否则返回null。

9、根据key删除元素
public V remove(Object key) {
	Entry<K,V> e = removeEntryForKey(key);
	return (e == null ? null : e.value);
}
调用的还是下面的方法
final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }


    这里while循环外面的很好看懂,我们讨论while循环里的。
Entry<K,V> next = e.next;把原有的链表截出表头元素,然后判断这个表头元素的key是否就是我们要找的key。如果找出的第一个元素就是的话,我们直接将这个链表的第一个元素删除就OK。
if (prev == e)
      table[i] = next;
    如果不是,则遍历这个链表,下图展示了这个过程:

步骤1、初始情况
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;

步骤2、没找到
Entry<K,V> next = e.next;
……..
prev = e;
e = next;
如果e这个元素不是要删除的话,则遍历下一个元素。

步骤3、找到
prev.next = next;
return e;
将prev的下一个元素指向e.next。这样就相当于删除了e
最后的结果如下:


未完待续。。。















文章评论

程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员都该阅读的书
程序员都该阅读的书
每天工作4小时的程序员
每天工作4小时的程序员
我的丈夫是个程序员
我的丈夫是个程序员
10个调试和排错的小建议
10个调试和排错的小建议
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我是如何打败拖延症的
我是如何打败拖延症的
编程语言是女人
编程语言是女人
Java程序员必看电影
Java程序员必看电影
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员的鄙视链
程序员的鄙视链
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员必看的十大电影
程序员必看的十大电影
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
一个程序员的时间管理
一个程序员的时间管理
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
 程序员的样子
程序员的样子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
代码女神横空出世
代码女神横空出世
鲜为人知的编程真相
鲜为人知的编程真相
程序员和编码员之间的区别
程序员和编码员之间的区别
老程序员的下场
老程序员的下场
如何成为一名黑客
如何成为一名黑客
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
中美印日四国程序员比较
中美印日四国程序员比较
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有