文档章节

hashMap实现原理

small达达
 small达达
发布于 2016/02/01 17:24
字数 1873
阅读 427
收藏 8

1、HashMap概述:

    1)HashMap实现了Map接口,与HashTable等效,除了HashMap是线程不同步的,且允许空value,空key;且不保证映射的顺序,特别是它不保证顺序恒久不变

    2)该实现提供了常量时间性能的基本操作,若注重迭代性能,则不要把初始化容量设置过高,(或加载因子过低),迭代时间与HashMap实例的“容量”(桶的数量)加key-value成正比

    3)HashMap实例的两个参数影响其性能,initial capacity(初始化容量),load Factor(加载因子)

        容量指的是:Hash表中桶的数量

        加载因子:决定了Hash表的容量何时自动增长

        当Entries的数量超过加载因子*当前容量,将会rehashed(内部数据结构将会被重构),容量扩展为2倍

    4)作为一般规则,默认加载因子大小为0.75,提供较高的值减少了空间上的消耗,但增加了时间成本(主要体现在get和put上,设置其初始化容量时需要考虑何时的entries和load factor,以减少rehash次数)

    5)该实现是不同步的,如果多线程并发访问hashMap,且至少一个线程修改map的结构,它必须从外部上锁(修改结构指的是任何添加和删除映射,仅仅修改key锁关联的value不属于结构修改),上锁方式:

    Map m = Collections.sychronizedMap(new HashMap());

    6)迭代器返回Collection视图都将快速失败:若map在迭代器创建之后修改结构,以任何方式除了迭代器的remove方法都将抛出ConcurrentmodificationException,所以,面对HashMap的并发修改,迭代器会快速失败,而不是在不确定的时间。


下面是HashMap类的方法:

void clear()   
          从此映射中移除所有映射关系。   
 Object clone()   
          返回此 HashMap 实例的浅表副本:并不复制键和值本身。   
 boolean containsKey(Object key)   
          如果此映射包含对于指定键的映射关系,则返回 true。   
 boolean containsValue(Object value)   
          如果此映射将一个或多个键映射到指定值,则返回 true。   
 Set<Map.Entry<K,V>> entrySet()   
          返回此映射所包含的映射关系的 Set 视图。   
 V get(Object key)   
          返回指定键所映射的值;如果对于该键来说,此映射不包含任何映射关系,则返回 null。   
 boolean isEmpty()   
          如果此映射不包含键-值映射关系,则返回 true。   
 Set<K> keySet()   
          返回此映射中所包含的键的 Set 视图。   
 V put(K key, V value)   
          在此映射中关联指定值与指定键。   
 void putAll(Map<? extends K,? extends V> m)   
          将指定映射的所有映射关系复制到此映射中,这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系。   
 V remove(Object key)   
          从此映射中移除指定键的映射关系(如果存在)。   
 int size()   
          返回此映射中的键-值映射关系数。   
 Collection<V> values()   
          返回此映射所包含的值的 Collection 视图


下面是HashMap的源码分析:

一、HashMap的数据结构

    HashMap是由线性表组成(每个节点存放一个Entry对象,该Entry对象为Entries链表的头结点),如图:


/**
     * 默认初始化容量大小-必须为2的倍数
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 最大容量值,会被构造器参数取代,但必须小于2的30次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认加载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     *必要时大小会进行调整,但length必须为2的次幂
     */
    transient Entry[] table;

    /**
     * map中拥有的映射数.
     */
    transient int size;

    /**
     * map进行resize的临界值
     */
    int threshold;

    /**
     * 加载因子
     */
    final float loadFactor;

    /**
     * 用来控制快速失败策略的标志变量,迭代器在初始化的时候会得到其值,在遍历过程中如果发生改变,则快速失败
     */
    transient int modCount;

   
    public HashMap(int initialCapacity, float loadFactor) {
        //初始化容量不允许小于0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //若大于最大容量,则设为最大容量值
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //加载因子不能小于0,
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        // 使得capacity 的大小为2的幂,至于为什么,请看下面
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }
下面是用于包装key-value映射关系的Entry,它是HashMap的静态内部类:
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
}
可以看到,Entry实现了接口Map.Entry,一个Entry对象对应map中的一组key-value映射,hash为 hash(key.hashCode())哈希函数后产生的值,也可以看出这是个链表数据结构,维护了一个后继节点的引用


二、HashMap如何解决Hash冲突:

Hash冲突指的是:具有不同的key通过hash函数映射却得到了相同的hash值

HashMap的解决方案是:分离链接法,即判断hash值是否相同,hash值相同,key值不同的Entry对象将以链表形式维护,而hash值相同,key值也相同的对象将进行覆盖


public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value);  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            //判断当前确定的索引位置是否存在相同hashcode和相同key的元素,如果存在相同的hashcode和相同的key的元素,那么新值覆盖原来的旧值,并返回旧值。  
            //如果存在相同的hashcode,那么他们确定的索引位置就相同,这时判断他们的key是否相同,如果不相同,这时就是产生了hash冲突。  
            //Hash冲突后,那么HashMap的单个bucket里存储的不是一个 Entry,而是一个 Entry 链。  
            //系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),  
            //那系统必须循环到最后才能找到该元素。  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
    }



这里也需要注意下addEntry方法:
void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }



这里,如果size++大于临界值,则会进行对Map结构进行resize,一下是对上述理论的测试代码:


package com.jdk;

import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/*
 * 测试HashMap代码
 */
public class testMap {
	public static void main(String[] args) {
		//HashMap<String, String> map = new HashMap<String, String>(20,0.75f);
		Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());
		// 默认tables大小为16,在resize方法中打断点进行测试,如果i<12则不会进行resize,如果i<13则会出现resize,所以超过12,则在初始化map的时候应该将初始化容量设置大一点
		// 将上面代码替换成HashMap<String, String> map = new HashMap<String, String>(20,0.75f);则不会进行resize
		for (int i = 0; i < 12; i++) {
			map.put("key" + i, "value" + i);
		}
		// 使用entryset()进行遍历
		Iterator iter = map.entrySet().iterator();
		while (iter.hasNext()) {
			//以下操作对map的结构进行了修改,所以会直接抛出java.util.ConcurrentModificationException
			map.put("test", "是不是会中断"); 
			map.remove("key4");
			
			Map.Entry entry = (Map.Entry) iter.next();
			// System.out.println(entry.getKey());
			System.out.println(entry.getValue());
		}
	}
}




© 著作权归作者所有

共有 人打赏支持
small达达
粉丝 6
博文 19
码字总数 7504
作品 0
太原
程序员
私信 提问
hashmap实现原理浅析

看了下JAVA里面有HashMap、Hashtable、HashSet三种hash集合的实现源码,这里总结下,理解错误的地方还望指正 HashMap和Hashtable的区别 HashSet和HashMap、Hashtable的区别 HashMap和Hashtab...

商者
2016/03/30
37
0
HashMap和HashSet的区别

HashMap和HashSet的区别是Java面试中最常被问到的问题。如果没有涉及到Collection框架以及多线程的面试,可以说是不完整。而Collection框架的问题不涉及到HashSet和HashMap,也可以说是不完整...

LCZ777
2014/03/29
0
0
详解 Java 8 HashMap 实现原理

HashMap 是 Java 开发过程中常用的工具类之一,也是面试过程中常问的内容,此篇文件通过作者自己的理解和网上众多资料对其进行一个解析。作者本地的 JDK 版本为 64 位的 1.8.0_171。参考资料...

☆★傲天★☆
08/17
0
0
Java:HashMap和Hashset的实现

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

樂天
2015/06/28
0
2
Java集合---大结局(总结概括终结篇)

文章写到这,感觉该做一个总结了,也是时候结束了, 最常用的集合类基本上已经写完了,剩下的就不再继续探索了,感兴趣的自行研究,应该还会有几篇番外篇,关于并发包JUC中的集合,如current...

起个名忒难
2017/11/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

spring学习笔记(二)spring 事件的使用

spring 中的事件 spring事件通过订阅发布 可以解耦操作 可以同步 可以异步 步骤 编写事件 通过继承org.springframework.context.ApplicationEvent 来编写事件 public ApplicationEvent(Obj...

NotFound403
昨天
11
0
特斯拉车主成功破解了自己Model 3汽车

据汽车博客Electrek消息,一位特斯拉车主成功破解了自己Model 3汽车,还在此基础上运行了Ubuntu。 这位叫trsohmers的网友表示,“功劳大多要归到Ingineerix的头上,他花了数月才找到初始的那...

linuxCool
昨天
3
0
Gitbook : random errors when using gitbook plugin on running "gitbook serve"

在执行gitbook serve时,会有不定的失败错误 参考问题 :#1309 解决方案: 更新gitbook版本,这个问题似乎是3版本的问题 , 官方也不打算在这个版本解决了。 更新 到最新版本后, 不再出现问...

ol_O_O_lo
昨天
1
0
提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字

提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字: 作者:王健茜;断断续续一个多月才读完了《中国文化的深层结构》,这并不是一本难懂的书,之所以读得慢,源于对书中观点的思...

原创小博客
昨天
3
0
高德地图-行政区域接口

1、获取全国各省信息 https://restapi.amap.com/v3/config/district?extensions=all&key=应用Key&s=rsv3&output=json 2、获取下级行政区域信息 https://restapi.amap.com/v3/config/distric......

voole
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部