`

HashMap原理

    博客分类:
  • Java
阅读更多

 

 

对于HashMap的理解如果只停留在hash数据结构的存储,key/value可以是null,那就太片面了,更深层次的理解HashMap,需要知道HashMap其实就是数组+链表,HashMap有个关于bucket(桶)的概念,这个bucket就是数组实现的,每个bucket里面可以存储的Entry<K,V>,这个Entry<K,V>可以是多个,当有多个时碰撞就发生了,当bucket里需要存储多个Entry<K,V>时使用链表存储,HashMap的基本结构就是这样的。下图来来自网络

 

通过查看Entry的源码,Entry中定义的一些类变量,证明bucket里面存储的Entry是一个链表结构

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//针对一下元素的引用
        int hash;
} 

 

HashMap中定义的一些默认常量,比如HashMap的默认容量, resize的尺寸,还有最重要的bucket是个Entry[]数组

// HashMap的默认初始容量 必须为2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 二进制1向左移动4位=16
//HashMap的最大容量,可以认为是int的最大值  
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空Entry[]
static final Entry<?,?>[] EMPTY_TABLE = {};
//用来存储数据的数组,所以说HashMap的底层存储是个数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

 

HashMap中put元素的过程:

1、根据key的hashcode获得bucket位置

2、如果bucket是空的,直接存入

3、如果bucket不为空,就发生了碰撞,这时把元素放在bucket中链表的头部

通过源码来分析put()操作的这一过程

public V put( K key, V value ) {
		//存储bucket的数组为空就初始化
		if ( table == EMPTY_TABLE ) {
			inflateTable(threshold);
		}
		//key为null时特殊处理,总是放在table[0]的位置
		if ( key == null ) {
			return putForNullKey(value);
		}
		//计算key的hashcode
		int hash = hash(key);
		//通过hashcode获取bucket的位置
		int i = indexFor(hash, table.length);
//遍历table[i]位置的bucket链表,查找相同的key,若找到则使用新的value替换掉原来的oldValue并返回oldValue,这就是hashcede碰撞发生时的种情况
		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;
			}
		}
//若没有在table[i]位置找到相同的key,则添加key到table[i]位置,新的元素总是在table[i]位置的第一个元素
		modCount++;
		addEntry(hash, key, value, i);
		return null;
	}
	void addEntry( int hash, K key, V value, int bucketIndex ) {
		//检查Entry[]大小,容量的75%扩大容量,减少碰撞发生
		if ( (size >= threshold) && (null != table[bucketIndex]) ) {
			resize(2 * table.length);//当前Entry[]大小*2
			hash = (null != key) ? hash(key) : 0;
			bucketIndex = indexFor(hash, table.length);
		}
		createEntry(hash, key, value, bucketIndex);
	}
	//这个方法就是真正的把key/value添加到Entry中的操作
	void createEntry( int hash, K key, V value, int bucketIndex ) {
		Entry<K, V> e = table[bucketIndex];
		table[bucketIndex] = new Entry<>(hash, key, value, e);
		size++;
	}

 

HashMap中get元素的过程:

1、根据key的hashcode获得bucket位置

2、如果bucket里面只有一个元素,这时性能最好的,直接取出

3、如果bucket中有多个元素,则通过key的equals()方法,在bucket中链表上查找

通过源码来分析get()操作过程

public V get( Object key ) {
		//ke为null时的处理
		if ( key == null ) {
			return getForNullKey();
		}
		//通过key获取Entry
		Entry<K, V> entry = getEntry(key);
		return null == entry ? null : entry.getValue();
}
final Entry<K, V> getEntry( Object key ) {
		if ( size == 0 ) {
			return null;
		}
		//对key进行hash获取bucket的位置
		int hash = (key == null) ? 0 : hash(key);
		//循环bucket里面的链表根据key的hash值及对key进行equals
		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 != null && key.equals(k))) ) {
				return e;
			}
		}
		return null;
}

 

减少碰撞发生可以提高HashMap的性能,一个存入HashMap的自定义对象都要覆写Object的hashcode()和equals(),覆写equals时有写原则

(1)自反性:就是说a.equals(a)必须为true。 

(2)对称性:就是说a.equals(b)=true的话,b.equals(a)也必须为true。 

(3)传递性:就是说a.equals(b)=true,并且b.equals(c)=true的话,a.equals(c)也必须为true。

 

计算bucket的算法,并没有使用key.hashcode()%Entry[].length的方式而是采用了如下方式,减少碰撞的发生,bucket的大小为2的幂时效率最高

 static int indexFor(int h, int length) {
        return h & (length-1);
}

 

resize是指Entry[]中被使用的位置大于Entry.length*0.75倍时,resieze就发生了,对原来的Entry[]进行扩容,默认Entry[]大小为16,也就是16*0.75=12,当Entry[]大小为16时,被使用的大小超过12个,就要对原有的Entry[]进行扩容,原有Entry[].length*2,通过源码来分析这个过程

void resize( int newCapacity ) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		//原有bucket=1<<30 = 1 073 741 824,时就创建一个大小为0x7fffffff的bucket
		if ( oldCapacity == MAXIMUM_CAPACITY ) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		//创建新的Entry[]
		Entry[] newTable = new Entry[newCapacity];
		//把当前Entry[]中的内容放到新的Entry[]中,并对它们在新的Entry[]中的位置重新计算
		transfer(newTable, initHashSeedAsNeeded(newCapacity));
		table = newTable;
                //重新计算需要扩容的临界值
		threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
	}

	void transfer( Entry[] newTable, boolean rehash ) {
		int newCapacity = newTable.length;
		for ( Entry<K, V> e : table ) {
			while ( null != e ) {
				Entry<K, V> next = e.next;
				if ( rehash ) {
					e.hash = null == e.key ? 0 : hash(e.key);
				}
				int i = indexFor(e.hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			}
		}
	}

 resize在以下方法中被调用到了,如果为了性能考虑也可以在初始化一个HashMap时就指定bucket大小,但最好是2的幂

void addEntry(int hash, K key, V value, int bucketIndex)
public void putAll(Map<? extends K, ? extends V> m) 

 

清空HashMap中的所有数据,其实就是把Entry[]数组全部置中为null,然后把Entry[].size设置为0

 public void clear() {
        modCount++;
        Arrays.fill(table, null);
        size = 0;
    }

 

hashmap中其它的一下方法,后续还会补充进来

 

 

以上源码来自jdk1.7,版本如下

java version "1.7.0_79"
Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)

 
 

 

 

 

 

 

 

 

  • 大小: 41.9 KB
  • 大小: 6 KB
分享到:
评论

相关推荐

    java HashMap原理分析

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

    HashMap原理.rar

    HashMap是Java编程语言中最常用的集合类之一,它属于`java.util`包,提供了一种以键值对形式存储数据的数据结构。HashMap的核心在于其高效的数据查找、...阅读“HashMap原理.pdf”文件,可以获得更深入的细节和示例。

    HashMap原理.docx

    ### HashMap原理详解 #### 一、HashMap简介与应用场景 HashMap是Java集合框架中一个非常重要的组成部分,它提供了基于键值对(key-value)映射的高效数据存储方式。由于其内部采用了数组加链表(以及红黑树优化)的...

    一线大厂BATJ面试题讲解-hashmap原理实现

    一线大厂BATJ面试题讲解-hashmap原理实现

    hashmap实现原理

    在深入探讨HashMap的实现原理之前,我们需要了解两个关键的接口方法:`hashCode()`和`equals()`。 根据《Effective JAVA》的建议,当重写`equals()`方法时,也应重写`hashCode()`方法。这是因为在HashMap中,`...

    HashMap原理的深入理解

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

    HashMap原理.pdf

    要理解HashMap的工作原理,首先需要了解它如何结合数组和链表的特点来提升性能。数组的特点是查找速度快,因为它们在内存中是连续分布的,这使得通过下标访问特定元素的时间复杂度是O(1)。但数组的缺点在于其大小是...

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

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

    hashMap工作原理

    详细介绍了hashMap原理,值得一看,对于面试者有很大帮助

    Java HashMap原理及实例解析

    Java HashMap原理及实例解析 Java HashMap是一种常用的数据结构,它提供了快速的查找、插入、删除操作。HashMap的键值对的存储方式是通过键值对来存储数据的,键是唯一的,不可以重复的,而值可以重复。 HashMap的...

    尚硅谷-深入java8的集合3:HashMap的实现原理.pdf

    本教程特点: 1.更适合零基础学员: ·自Java语言起源始,循序渐进,知识点剖析细致且每章配备大量随堂练习,让你步步为营,学得透彻、练得明白 ·拒绝晦涩难懂的呆板教学,宋老师语言生动幽默,举例形象生动深入浅...

    HashMap底层原理.md

    HashMap底层原理.md

    java无锁hashmap原理与实现详解

    ### CAS操作原理 CAS操作包含三个参数:内存地址V、预期值A和新值B。如果内存地址V的值等于预期值A,则将V的值更新为新值B,整个过程是原子性的。如果V的值不是A,则操作失败,不会进行任何修改。Java中的`...

    HashMap原理分析及性能优化

    文章目录一.HashMap是什么二.HashMap继承类对比分析三.HashMap源码相关单词含义四.HashMap如何确定哈希桶数组索引位置五. HashMap 的 put 方法分析六.HashMap扩容机制七.HashMap线程安全性 一.HashMap是什么 ...

    HashMap底层原理

    HashMap的底层原理主要依赖于哈希表,这是一种数据结构,它通过计算键的哈希码来实现高效的查找操作。 在HashMap中,每个元素都是一个键值对,存储在一个Entry对象中。当向HashMap添加键值对时,首先会计算键的哈希...

    HashMap讲解注释版本.java

    对HashMap 源码逐行进行注释,带你深入理解HashMap原理,使面试不在困难,

    图解hashMap工作原理

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

    HashMap底层原理.pdf

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

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

    在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...

Global site tag (gtag.js) - Google Analytics