`
g21121
  • 浏览: 694744 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Map实现之HashMap(结构及原理)

 
阅读更多

        java.util包中的集合类包含 Java 中某些最常用的类。最常用的集合类是 List 和 Map。List 的具体实现包括 ArrayList 和 Vector,它们是可变大小的列表,比较适合构建、存储和操作任何类型对象元素列表。List 适用于按数值索引访问元素的情形。

        Map 则提供了一个更通用的元素存储方法。Map 集合类用于存储元素对(称作“键”和“值”),其中每个键映射到一个值。从概念上而言,您可以将 List 看作是具有数值键的 Map。而实际上,除了 List 和 Map 都在定义 java.util 中外,两者并没有直接的联系。

        Map接口的实现类有很多,其中HashMap就是比较重要的一个实现,本文就以HashMap为主重点介绍。

        HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

        HashMap结合了ArrayList与LinkedList两个实现的优点,,虽然HashMap并不会向List的两种实现那样在某项操作上性能较高,但是在基本操作(get 和 put)上具有稳定的性能。

 

        首先从成员变量开始一点点的来了解HashMap和上述几个概念。

 

        1.HashMap的成员变量:

/**
 * 初始默认容量(必须为2的幂次方)
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
 * 最大容量,如果被指定为一个更高的值必须为2的幂次方,并且小于1073741824.(1<<30)
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认负载因子/负载系数
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 内部实现表, 必要时调整大小,其长度亦为2的幂次方
 */
transient Entry[] table;

/**
 * map中添加的元素个数
 */
transient int size;

/**
 * 扩容临界值,当size达到此值时进行扩容 (容量乘以负载因子).
 */
int threshold;

/**
 * 内部实现表的负载因子
 */
final float loadFactor;

/**
 * 操作数,可以理解为map实例被操作的次数,包括添加,删除等等
 */
transient volatile int modCount;

        HashMap其内部实现是一个Entry数组table,而Entry就是保存相应键值的实体。table数组默认大小为16,我们也可以在初始化时指定更大的值,但指定值必须为2的幂次方。

        通过对ArrayList的学习了解到ArrayList其内部实现也是数组,当被添加的元素超出数组的容纳极限时,ArrayList会对内部数组进行一次“扩容”,从而可以添加新的元素。

        在HashMap中也有类似的概念,HashMap并不会像ArrayList一样直到数组都满了的情况下才去“扩容”,而是根据负载因子(load factor)来进行判断。

        举例来说:HashMap实例中table数组的默认大小为16,负载因子为0.75,当添加元素个数大于等于12(16*0.75)时就会进行扩容。

        所以说容量和负载因子直接影响着table数组是否扩容,什么时机扩容,进而影响这HashMap实例的性能。

        当我们在初始化时可以指定HashMap实例的容量大小,当指定大小不为2的幂次方时,如下:

Map map=new HashMap(131);

        请问初始化完成HashMap内table的长度是多少? 答案为:256

        其实只要打开HashMap的构造函数源代码就明白为什么了,以下为源代码:

public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: "
				+ initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: "
				+ loadFactor);

	// Find a power of 2 >= initialCapacity
	int capacity = 1;
	while (capacity < initialCapacity)
		capacity <<= 1;

	this.loadFactor = loadFactor;
	threshold = (int) (capacity * loadFactor);
	table = new Entry[capacity];
	init();
}

        关键在于这两行:

while (capacity < initialCapacity)
	capacity <<= 1;

 

        如果initialCapacity(指定大小)大于capacity(原或初始化大小)时,就会不断循环进行位移赋值计算,相当于capacity=capacity *2.直至capacity 大于或等于我们指定的大小。如果指定的大小正好为2的N次幂时两个值便会相等,进而终止计算;如果指定大小不符合条件时,capacity 就会是刚好大于指定大小的那个2的N次幂的数。

        所以,在上面我们指定大小为131,大于131并且为2的的N次幂的数就为256,所以此时就会按256来初始化table.

 

        2.Entry 元素

        与LinkedList类似,HashMap也是采用Entry内部类来存储实际元素信息,以下是Entry的源代码(省略部分代码):

static class Entry<K, V> implements Map.Entry<K, V> {
	final K key;
	V value;
	Entry<K, V> next;
	final int hash;
}

        Entry中包括4个成员变量,其中key为键,value为值,next指向下一个节点元素,hash为hash值。Entry通过next属性可以寻找到下一个节点的元素,进而通过遍历就可以找到相应key下存储的信息。

 

        3.HashMap设置元素

        Map通过put方法来在Map实例中关联指定值与指定键。如果该实例已经包含了一个该键的映射关系,则旧值被替换。

        示例如下:

Map map = new HashMap();
map.put("user1", "小明");
map.put("user2", "小强");
map.put("user3", "小红");
System.out.println("user1:" + map.get("user1"));
System.out.println("user2:" + map.get("user2"));
System.out.println("user3:" + map.get("user3"));
map.put("user2", "小龙");
System.out.println("user1:" + map.get("user1"));
//打印结果
user1:小明
user2:小强
user3:小红
user1:小明

        首先,创建了一个HashMap的实例map,此时map实例中的table数组会默认初始化,创建一个长度为DEFAULT_INITIAL_CAPACITY=16的空数组。

        然后,调用put方法将一对键、值(key,value)保存。当已存在Map实例中已存在指定key的映射时,会将新指定的value覆盖原value。

        与LIst的相关实现add方法一样,HashMap的put方法是设置元素的入口,在put的过程中会进行一系列的判断与操作,所以只有将put方法理解透彻后HashMap的内部结构与机制才会更加清晰。

        HashMap进行put操作时按以下步骤执行:

        1)判断key是否为空,如果为空则调用设置null的专有方法。

        2)计算key的hash值。

        3)通过hash与table数组的长度计算出该元素所要放置的数组下标。

        4)遍历该下标下的Entry元素链,如果找到与指定key相同的Entry则直接替换该Entry的value值并返回。

        5)如果未找到则添加一个新元素至该下标下的元素链前端。

        以下是一张官网上对于put操作流程的描述图片,可以作为参考:


        以下是put方法的源代码,其中我已经加入了相关描述便于大家理解:

/**
 * 设置指定值
 */
public V put(K key, V value) {
	//1.首先判断key是否为null
	if (key == null)
		//如果为null则调用putForNullKey方法
		return putForNullKey(value);
	//2.计算key的hash值
	int hash = hash(key.hashCode());
	//3.根据计算后的hash值与table数组长度计算该key应放置到table数组的那个下标位置
	int i = indexFor(hash, table.length);
	//4.遍历该下标下的所有Entry,如果key已存在则覆盖该key所在Entry的value值
	for (Entry<K, V> e = table[i]; e != null; e = e.next) {
		Object k;
		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;
		}
	}

	modCount++;
	//5.如果该key不存在则新添加Entry元素至数组指定位置,并且该Entry作为此下标元素链的头部
	addEntry(hash, key, value, i);
	return null;
}
 
        4.HashMap内部结构
        通过对put方法的流程分析,我们基本已经了解HashMap其内部实现的机制与原理,那么来总结一下HashMap初始化及添加元素的过程(以默认值为例):
        (1) 初始化HashMap实例,初始化其内部数组table:
this.loadFactor = DEFAULT_LOAD_FACTOR;//0.75f
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//16*0.75=12
table = new Entry[DEFAULT_INITIAL_CAPACITY];//16
        此时table被初始化创建,长度为16。
        (2) 当第一次put元素时,此时HashMap实例中并没有添加任何元素,所以put方法会直接调用addEntry方法:
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        首先,会先获取该下标(bucketIndex)下原Entry信息,因为table并未设置任何值,所以此时e为null。
        然后,创建一个新的Entry实例,其next属性指向e,并将此实例赋值给table[bucketIndex]。
        (3) 当更新HashMap实例中已有key的value内容时:
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
    }
}
        如果HashMap实例中已经put了该key则只需遍历找到该节点Entry,更新其value并返回,所以更新已有key的操作不会调用addEntry方法。
        (4) 此时HashMap实例的内部结构如下图所示:


        HashMap采用此种存储元素的方式是结合了ArrayList与LinkedList两者的优点,虽然单纯某项操作的性能上并不比二者之一高,但这种方式的好处就是存储与获取性能平稳,并不会出现剧烈波动的情况。
 
        5.HashMap获取元素
        既然已经了解了HashMap的内部结构已经设置元素时的相关操作步骤,那么获取元素其实也就比较容易理解了,首先根据指定的key去计算数组下标,然后遍历该下标下的Entry链,最后返回。
        以下是get方法的源代码,与put方法的基本流程大致相同:
/**
 * 返回指定key的value
 */
public V get(Object key) {
	// 1.判断可以是否为null
	if (key == null)
		return getForNullKey();
	// 2.计算key的hash值
	int hash = hash(key.hashCode());
	// 3.遍历table指定下标下的Entry链
	for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
		Object k;
		// 4.如果找到则返回该Entry的value
		if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
			return e.value;
	}
	// 5.未找到则返回null
	return null;
}

        6.HashMap移除元素
        HashMap实现了Map接口的remove方法,所以可以通过remove方法移除已经添加的元素:
Map map = new HashMap();
map.put("user1", "小明");
map.put("user2", "小强");
map.put("user3", "小红");
map.remove("user2");
System.out.println("user1:" + map.get("user1"));
System.out.println("user2:" + map.get("user2"));
System.out.println("user3:" + map.get("user3"));
//打印结果:
user1:小明
user2:null
user3:小红
        当主动调用remove方法时,会根据指定的key删除该节点元素。
        以下是remove方法的源代码:
/**
 * 删除指定key下内容
 */
public V remove(Object key) {
	Entry<K, V> e = removeEntryForKey(key);
	return (e == null ? null : e.value);
}

/**
 * 根据指定key删除元素
 */
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;
}
        remove方法调用了另一个方法removeEntryForKey,removeEntryForKey方法会循环遍历指定下标下所有Entry节点元素,如果该key存在则修改该节点前一个节点的next指向,从而达到把该Entry节点移除Entry链的目的。
        注意HashMap的remove操作一样不会引起“减容”操作,这样就不会影响性能。
 
        7.HashMap的遍历
        通常情况下Map的使用者清楚该Map实例中有那些key,通过get(key)方法就可以直接将所有元素取出,但某些情况下这种做法产生的代码将是一次性代码,无法共用。
        HashMap的遍历通常采用以下几种方式:
        1)通过entrySet()方法可以获取HashMap实例所有Entry的Set返回,所以通过entrySet方法返回并迭代可以获取所有Entry元素:
Map map = new HashMap();
map.put("user1", "小明");
map.put("user2", "小强");
map.put("user3", "小红");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
	Map.Entry entry = (Map.Entry) iter.next();
	Object key = entry.getKey();
	Object value = entry.getValue();
	System.out.println("key:" + key + ";value:" + value);
	// 然后移除元素
	if (key.toString().equals("user1")) {
		iter.remove();
	} else if (key.toString().equals("user2")) {
		entry.setValue("小海");
	}

}
System.out.println(map.get("user1"));
System.out.println(map.get("user2"));
System.out.println(map.get("user3"));

// 打印结果:
key:user2;value:小强
key:user1;value:小明
key:user3;value:小红
null
小海
小红
        此种方式操作简单,代码量少,效率较高,且可以直接操作元素,是常用的手段之一。
        2)Map还提供了keySet方法,用于返回所有key的Set形式,然后迭代此Set再通过get方法就可以获取相应元素的value:
Map map = new HashMap();
map.put("user1", "小明");
map.put("user2", "小强");
map.put("user3", "小红");
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
	Object key = iter.next();
	Object value = map.get(key);
	System.out.println("key:" + key + ";value:" + value);
	// 然后移除元素
	if (key.toString().equals("user1")) {
		iter.remove();
	}
}
System.out.println(map.get("user1"));
System.out.println(map.get("user2"));
System.out.println(map.get("user3"));

// 打印结果:
key:user2;value:小强
key:user1;value:小明
key:user3;value:小红
null
小强
小红
        此种方式先需要将所有key遍历后返回,再通过get方法来获取元素,如果单纯需要操作Map实例中的个别节点元素时效率尚可,如果需要大规模获取和修改时效率不如第一种。所以两种方式选择那种需要视情况而言,并没有绝对。
        3)通过values方法直接返回所有value:
Map map = new HashMap();
map.put("user1", "小明");
map.put("user2", "小强");
map.put("user3", "小红");
//转换成数组
String[] names= (String[]) map.values().toArray(new String[map.size()]);
for (String name : names){
	System.out.println(name);
}
//采用迭代
Collection nameArray =  map.values();

Iterator iter = nameArray.iterator();

while (iter.hasNext()) {

 String name=iter.next().toString();

 System.out.println(name);

}
// 打印结果:
小强
小明
小红
        此种方式简单明了,适用于直接获取所有value的情况,可以直接迭代或者转换成数组,当直接显示value的情况下比较适用。
        HashMap的基本结构及内部实现原理至此已经比较清晰,下一篇着重来了解下HashMap其内部几种算法的原理及相关性能。
8
1
分享到:
评论
1 楼 夏日娃 2015-03-04  

相关推荐

    深入Java集合学习系列:HashMap的实现原理

    HashMap是一个基于哈希表的数据结构,它实现了Map接口,提供了快速的存取功能。本文将深入探讨HashMap的内部机制,包括其构造、工作原理、哈希函数、冲突解决策略以及扩容机制。 首先,HashMap的基本结构是由数组...

    HashMap的实现原理

    ### HashMap的实现原理 #### 1. HashMap概述 HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值...

    自定义map实现java的hashmap

    在Java编程中,HashMap是一个非常重要的数据结构,它实现了Map接口,提供了键值对的存储功能,具有快速存取和高效查找的特点。HashMap基于哈希表(也称为散列表)原理,通过键对象的哈希码来定位元素,进而实现O(1)...

    java HashMap原理分析

    Java HashMap是一种基于哈希表的数据结构,它的存储原理是通过将Key-Value对存储在一个数组中,每个数组元素是一个链表,链表中的每个元素是一个Entry对象,Entry对象包含了Key、Value和指向下一个Entry对象的引用。...

    HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别.docx

    HashMap是Java中常用的一种数据结构,它基于哈希表实现,提供快速的键值对存储和检索。HashMap的核心原理是通过散列函数将键对象转换为哈希码,然后使用这个哈希码来确定键值对在内部数组中的位置。哈希函数的设计...

    HashMap底层实现原理共6页.pdf.zip

    《HashMap底层实现原理》 HashMap是Java编程语言中一个非常重要的数据结构,它在实际开发中被广泛应用。...在理解和掌握了HashMap的实现原理后,我们可以更好地利用这一数据结构来提高代码的性能。

    HashMap底层原理.pdf

    HashMap是Java中非常常见的一种数据结构,主要用于存储键值对,其核心原理是通过哈希算法将键映射到数组中的位置来实现快速访问。本文将详细介绍HashMap的底层原理,包括其内部实现结构、关键字段的作用、以及JDK ...

    图解hashMap工作原理

    hashMap基本工作原理,图解分析,基础Map集合

    HashMap新增数据原理.docx

    HashMap是Java中广泛使用的数据结构之一,它在处理大量数据时能提供高效的操作性能。在Java 1.8中,HashMap的实现采用了数组+链表+红黑树的混合结构,以解决哈希冲突并优化查询效率。本文将深入解析HashMap的put方法...

    易语言HashMap类

    易语言HashMap类是一种在易语言编程环境中实现的高效数据结构,它主要用于存储键值对(key-value pairs),提供快速的数据存取。HashMap类基于哈希表(Hash Table)原理,通过计算键的散列值来确定数据在内存中的...

    Jdk1.8中的HashMap实现原理.pdf

    HashMap是Java编程语言中广泛使用的数据结构之一,它是基于哈希表实现的Map接口非同步实现。HashMap允许使用null值和null键,但不保证映射的顺序,尤其不保证这种顺序的持久性。在JDK1.8中,HashMap的数据结构发生了...

    hashMap基本原理,内存知识

    HashMap 是 Java 中最常用的 Map 实现类,因其查询速度快且可以存储大量数据,故广泛应用于各类 Java 应用程序中。HashMap 的特点是:底层使用哈希表,查询速度快,实现了 Map 接口,且是一个无序的集合,存储元素...

    源码解析jdk8.0集合:HashMap的底层实现原理.pdf

    - modCount:HashMap结构修改的计数器。 在JDK 8.0版本中,HashMap内部实现了懒惰初始化,也就是说只有在第一次使用时才会初始化数组table。当使用put方法插入键值对时,如果键对应的哈希值没有冲突,直接放到数组...

    HashMap-hash原理

    为了实现高效的数据存取操作,`HashMap`内部采用了数组加链表(JDK 1.8以前)或数组加链表/红黑树(JDK 1.8及以后版本)的数据结构。本文将重点解析`HashMap`中hash算法的核心原理及其优化细节。 #### 二、计算Key...

    Hashmap实现了Map接口的底层实现.docx

    HashMap是Java编程语言中一种非常重要的数据结构,它实现了Map接口,允许存储键值对,且支持null键和null值。HashMap的底层实现基于数组和链表,这使得它具有较快的查找速度。以下是关于HashMap的详细说明: 一、...

    深入arraylist,linkedlist,hashmap,hashset源码(2012/3/18)

    在Java编程语言中,ArrayList、LinkedList、HashMap和HashSet是四个非常重要的集合类,它们分别代表了不同类型的数据结构。...对于开发人员来说,掌握这些基础数据结构的实现原理是提高编程技能的重要一步。

    用hashmap实现词典查询

    本话题主要关注如何利用HashMap这一数据结构来实现词典查询,以提供快速、便捷的字典服务。HashMap是Java编程语言中的一种内置数据结构,它提供了O(1)的平均时间复杂度来执行查找、插入和删除操作,这使得它成为构建...

    HashMap原理的深入理解

    HashMap是基于哈希表的Map接口的非同步实现,提供了所有可选的映射操作,并允许使用null值和null键。HashMap储存的是键值对,HashMap很快。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的底层...

    Java集合,HashMap底层实现和原理(1.7数组+链表与1.8+的数组+链表+红黑树) 数组和链表.pdf

    在Java集合中,HashMap是一个常用的数据结构,它基于Map接口实现,元素以键值对的方式存储,并且允许使用null键和null值。由于key不允许重复,因此只能有一个键为null。HashMap不能保证插入元素的顺序,它是无序的,...

Global site tag (gtag.js) - Google Analytics