文档章节

hashMap实现原理

small达达
 small达达
发布于 2016/02/01 17:24
字数 1873
阅读 426
收藏 8
点赞 1
评论 0

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 ⋅ 0

Java:HashMap和Hashset的实现

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

樂天 ⋅ 2015/06/28 ⋅ 2

HashMap和HashSet的区别

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

LCZ777 ⋅ 2014/03/29 ⋅ 0

Java集合---大结局(总结概括终结篇)

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

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

HashMap-你可能需要知道这些

HashMap是Android程序员(当然也包括Java程序员)经常使用的映射数据类型,伴随着JDK的版本更新,JDK1.8相比1.7对HashMap的底层实现了一些优化,尤其是红黑树这个点(现在面试的时候基本都会问...

24K男 ⋅ 2017/10/09 ⋅ 0

Java集合框架知识及HashMap和HashSet的区别

HashMap和HashSet的区别 HashSet实质 (1)HashSet是set的一个实现类,hashMap是Map的一个实现类,同时hashMap是hashTable的替代品(为什么后面会讲到). (2)HashSet以对象作为元素,而HashMap以(ke...

qq_36523667 ⋅ 03/17 ⋅ 0

HashTable原理和底层实现

1. 概述 上次讨论了HashMap的结构,原理和实现,本文来对Map家族的另外一个常用集合HashTable进行介绍。HashTable和HashMap两种集合非常相似,经常被各种面试官问到两者的区别。 对于两者的区...

道可 ⋅ 01/27 ⋅ 0

Java常见面试题及答案 21-30(集合类)

21.HashMap的工作原理是什么? HashMap内部是通过一个数组实现的,只是这个数组比较特殊,数组里存储的元素是一个Entry实体(jdk 8为Node),这个Entry实体主要包含key、value以及一个指向自身的...

t4i2b10x4c22nf6a ⋅ 2017/12/18 ⋅ 0

HashMap, HashTable, HashSet分析

HashMap分析: 其主要特性:(key-value)存储,key-value可为NULL, 非线程安全。 其主要属性: //默认容量微16static final int DEFAULTINITIALCAPACITY = 1 << 4;//最大容量2^30static fina...

ihaolin ⋅ 2014/03/11 ⋅ 0

JDK源码阅读(三)、LinkedHashMap

一、LinkedHashMap原理 LinkedHashMap继承自HashMap,所以,它有hashMap的全部特性,它内部采用存储数据额的节点继承自HashMap的node。有一个before与after用于维护插入或者访问的顺序。它内...

zq17865815296 ⋅ 03/28 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

设计模式--装饰者模式

装饰者模式 定义 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比生成子类更为灵活。 通用类图 意图 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比...

gaob2001 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部