当前位置:首页 > 资讯 > 开源软件 > 正文

HashMap简单实现原理的理解

发表于: 2014-02-17   作者:110hxl   来源:转载   浏览次数:
摘要: 正常情况下,Map的key和Value都可以用数组实现,一边ArrayList是key的keys,另一边是ArrayList value的values。通过key获取value的方式是这样的values.get(keys.indexOf(key)).然而,数组的长度是有限的。不符合map可以无限放入元素的要求。所以要对这个数组进行特殊的要求。那就是同一个数组的index可以存放多个值,只是这些相同

正常情况下,Map的key和Value都可以用数组实现,一边ArrayList是key的keys,另一边是ArrayList value的values。

通过key获取value的方式是这样的values.get(keys.indexOf(key)).

然而,数组的长度是有限的。不符合map可以无限放入元素的要求。所以要对这个数组进行特殊的要求。

那就是同一个数组的index可以存放多个值,只是这些相同index的hascode值不同,这样就能把他们却别开了。同时也就实现无限个元素要求了(用数组实现主要是性能的优势)。那么要确定value就要计算hascode和数组下标。

数组不直接执行value的值,而是用equals()方法线性的查找;正常情况下这样的查找方式也会慢,但是只要hascode方法设计的合理,每个插槽将会只有少量的value.这样查找也就快很多;

import java.util.Map;

public class MapEntry<K,V> implements Map.Entry<K, V> {
	private K key;
	private V value;
	public MapEntry(K key, V value) {
		this.key = key;
		this.value = value;
	}
	@Override
	public K getKey() {
		return key;
	}
	@Override
	public V getValue() {
		return value;
	}
	@Override
	public V setValue(V value) {
		V result = this.value;
		this.value =value;
		return result;
	}
	@Override
	public int hashCode() {
		return (key == null ? 0:key.hashCode())^(value == null ? 0: value.hashCode());
	}
	@Override
	public boolean equals(Object obj) {
		if(!(obj instanceof MapEntry)) {
			return false;
		}
		MapEntry me = (MapEntry)obj;
		return (key ==null ? me.getKey() == null : key.equals(me.getKey())) &&
				(value == null ? me.getValue()==null : value.equals(me.getValue()));
	}
	@Override
	public String toString() {
		return key+"="+value;
	}
}



import java.util.AbstractMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

public class SimpleHashMap<K,V> extends AbstractMap<K, V> {
	static final int SIZE = 997;
	/**集合类型数组,数组的每个元素都是一个List集合类型**/
	LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
	public V put(K key, V value) {
		V oldValueV = null;
		/**根据hascode对数组长度求模,计算得出应该放入数组的index位置**/
		int index = Math.abs(key.hashCode())%SIZE;
		if(buckets[index] == null) {
			/**如果该下标下还没有集合,则创建**/
			buckets[index] = new LinkedList<MapEntry<K, V>>();
		}
		LinkedList<MapEntry<K, V>> bucket = buckets[index];
		/**把传进来的key和value封装为MapEntry类型**/
		MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
		/**假设在该数组index下的机会里找不到与pair对应的值**/
		boolean found = false;
		ListIterator<MapEntry<K, V>> it = bucket.listIterator();
		while(it.hasNext()) {
			MapEntry<K, V> iPair = it.next();
			if(iPair.getKey().equals(key)) {
				/**如果已经存在,则替换掉**/
				oldValueV = iPair.getValue();
				it.set(pair);
				found = true;
				break;
			}
		}
		if(!found) {
			/**如果不存在,则把封装后的MapEntry对象加入的集合中**/
			buckets[index].add(pair);
		}
		return oldValueV;
	}
	public V ge(Object key) {
		/**已同样的方式计算出应该的index**/
		int index = Math.abs(key.hashCode())%SIZE;
		if(buckets[index]==null) {
			/**对应的index里没有机会**/
			return null;
		}
		for(MapEntry<K, V> iPair : buckets[index]) {
			if(iPair.getKey().equals(key)) {
				/**对该index下的机会进行查找,比较MapEntr的key值**/
				return iPair.getValue();
			}
		}
		return null;
	}
	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K,V>>();
		for(LinkedList<MapEntry<K, V>> bucket : buckets) {
			if(bucket == null) continue;
			for(MapEntry<K, V> mpair : bucket) {
				/**用2个for循环,遍历这个二维的集合,把遍历到的每个值放到Set里**/
				set.add(mpair);
			}
		}
		return set;
	}
	public static void main(String[] args) {
		SimpleHashMap<String, String> mMap = new SimpleHashMap<String,String>();
		mMap.put("YYY", "yyy");
		mMap.put("QQQ", "qqq");
		mMap.put("AAA", "aaa");
		mMap.put("GGG", "ggg");
		System.out.println(mMap);
		System.out.println(mMap.get("GGG"));
		System.out.println(mMap.entrySet());
	}
}


摘自thinking in java

HashMap简单实现原理的理解

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
开写之前,我想先问两个问题:为什么是数据结构,什么是算法? 【Java数据结构和算法(第二版)】写道
HashMap内部数据结构 HashMap内部采用数组和链表结合的方式来存取数据(见下图)。这种方式有什么好
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null
1. HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允
0.参考文献: hash算法 (hashmap 实现原理) Java实现的散列表 1.HashMap的数据结构   数组的特点
hash算法 (hashmap 实现原理) Java实现的散列表 1.HashMap的数据结构   数组的特点是:寻址容易,
http://zhangshixi.iteye.com/blog/673789 转:http://www.iteye.com/topic/539465 Hashmap是一种非
看源码可以知道HashMap内部是由一个 Entry[] table组成 Entry的定义如下 static class Entry<K,V
1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。 数
1.HashMap的数据结构 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号