hash表是一种常见的数据结构,主要是通过hash算法将数据尽可能的散列开来存放,当要查找某一数据时,可以通过hash算法直接定位,节省了对比查找的时间。map是一种key、value形式的键值对,将hash表和map结合即形成了HashMap。
在Java中HashMap的数据是以Entry<key,value>数组的形式存放的,HashMap通过对key进行hash运算得到一个数组下标,然后将数据存放到Entry<key,value>数组对应的位置,又因为不同的key进行hash运算可能会得到一个相同的数组下标,为了解决碰撞覆盖冲突,所以Entry<key,value>本身又是一个链表的结构,即以后不同的key相同数组下标的数据的next会被赋值为已存在Entry<key,value>链表,新的Entry会替换数组值。
HashMap的存储数据的示例图如下:
HashMap 的put方法的源码解析
public V put(K key, V value) { if (key == null) return putForNullKey(value); // HashMap接收key为null的数据 int hash = hash(key.hashCode()); //对key的hashCode再进行hash运算 int i = indexFor(hash, table.length);//根据hash值和entry数组的大小计算出新增数据应该存放的数组位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { // for循环遍历找到的数组下标的entry,如果hash值和key都相等,则覆盖原来的value值 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++; //如果上面for循环没有找到相同的hash和key,则增加一个entry addEntry(hash, key, value, i); return null; }
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; //找到下标的entry //new 一个新的entry,赋值给当前下标数组 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; //即将原来数组下标对应的entry赋值给新的entry的next key = k; hash = h; }
(1)hash值相同且key相等数据将被覆盖。
(2)添加新的entry时,将已存在的数据下标的entry(可能是null)赋值给新entry的next,新entry将替换原数组下标的值。
HashMap的get方法源码解析
public V get(Object key) { //key为null时特别处理 if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //indexFor(hash, table.length) 根据hash值和数组长度计算出下标,然后遍历Entry链表 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.equals(k))) return e.value; } return null; }
总结
- 一个对象当HashMap的key时,必须覆盖hashCode()和equals()方法,hashCode()的返回值尽可能的分散。
- 当HashMap的entry的数组足够大,key的hash值足够分散时,即是可以实现一个entry数组下标最多只对应了一个entry,此时get方法的时间复杂度可以达到O(1)。
- 在数组长度和get方法的速度上要达到一个平衡。数组比较长碰撞出现的概率就比较小,所以get方法获取值时就比较快,但浪费了比较多的空间;当数组长度没有冗余时,碰撞出现的概率比较大,虽然节省了空间,但会牺牲get方法的时间。
- HashMap有默认的装载因子loadFactor=0.75,默认的entry数组的长度为16。装载因子的意义在于使得entry数组有冗余,默认即允许25%的冗余,当HashMap的数据的个数超过12(16*0.75)时即会对entry数组进行第一次扩容,后面的再次扩容依次类推。
- HashMap每次扩容一倍,resize时会将已存在的值从新进行数组下标的计算,这个是比较浪费时间的。在平时使用中,如果能估计出大概的HashMap的容量,可以合理的设置装载因子loadFactor和entry数组初始长度即可以避免resize操作,提高put的效率。
- HashMap不是线程安全的,多线程环境下可以使用Hashtable或ConcurrentHashMap。
相关推荐
这篇集合总结一共包括十二节,介绍了一些接口和实现类的底层源码以及基本的增加、删除元素等的操作(包括List、Map、Set接口、ArrayList、Vector、LinkedList、HashSet、TreeSet、HashMap、TreeMap等实现类)。...
之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。 HashMap实现了Map...
面试必考之HashMap源码分析与实现.mp4 │ │ │ ├─2.探索JVM底层奥秘ClassLoader源码分析与案例讲解 │ │ 2.探索JVM底层奥秘ClassLoader源码分析与案例讲解.wmv │ │ │ ├─3.锁、分布式锁、无锁实战全局性ID...
集合源码分析 JAVA: 基本语法 static 修饰变量 方法 静态块(初始化块 构造函数 ) 静态内部类() 静态导包 final() transient() foreach循环原理() volatile底层实现() equals和hashcode(, ) string,stringbuffer和...
源码分析 : ArrayList 源码+扩容机制分析 HashMap(JDK1.8)源码+底层数据结构分析 ConcurrentHashMap 源码+底层数据结构分析 IO IO 基础知识总结 IO 设计模式总结 IO 模型详解 并发 知识点/面试题总结 : (必看 ) ...
Java基础:集合类、HashMap/HashTable/CurrencyHashMap这几个的区别以及不JDK版本的区别、其他面向对象的语法,NIO,BIO,AIO; JVM:虚拟机结构,内存模型,双亲委派模型,内存溢出举例说明,垃圾回收算法,四大...
源码分析: ArrayList 源码+扩容机制分析 HashMap(JDK1.8)源码+底层数据结构分析 ConcurrentHashMap 源码+底层数据结构分析 IO IO 基础知识总结 IO 设计模式总结 IO 模型详解 并发 知识点/面试题总结 : (必看 ) ...
文章目录一.HashMap是什么二.HashMap继承类对比分析三.HashMap源码相关单词含义四.HashMap如何确定哈希桶数组索引位置五. HashMap 的 put 方法分析六.HashMap扩容机制七.HashMap线程安全性 一.HashMap是什么 ...
从源码角度分析Java中常用集合类的扩容机制 从这一篇开始,会陆续通过笔记来整理和记录之前看过的各种Java集合相关的知识点,主要包括List和Map。今天这一篇主要整理一下集合扩容相关的知识,涉及到的集合框架有:...
源码分析:ArrayList、Vector、LinkedList、HashMap、ConcurrentHashMap、HashSet、LinkedHashSet and LinkedHashMap 线程状态、线程机制、线程通信、J.U.C 组件、JMM、线程安全、锁优化 磁盘操作、字节操作、字符...
11.1 Java集合框架概述264 11.2 Collection接口264 11.2 Set接口实现类266 11.2.1 实现类HashSet267 11.2.2 实现类LinkHashSet270 11.2.3 实现类TreeSet272 11.3 List接口实现类277 11.3.1 实现类ArrayList277 ...
4: 源码分析分析讲的特别到位,尤其是HashMap的工作原理和源码分析,真正的把jdk源码翻了一遍,要是拿着这个去面试绝对是秒杀级神器。 5:使用多线程模拟用户去ATM取钱讲的也非常不错,后续还提了一个小Timer定时任务...
7.1 Java集合概述 241 7.2 Collection和Iterator接口 243 7.2.1 使用Iterator接口遍历集合元素 244 7.2.2 使用foreach循环遍历集合元素 246 7.3 Set接口 247 7.3.1 HashSet类 247 学生提问:hashCode方法对于...
Spring源码分析之IoC.docx 关于线程和线程池的学习与使用.docx 深入理解JVM垃圾回收机制.docx 深入理解多线程实现的另一种方式Callable.docx 红黑树简介.docx 线程死锁及解决办法.docx 线程锁之重入锁.docx 线程间的...
源码分析:ArrayList、Vector、LinkedList、HashMap、ConcurrentHashMap、HashSet、LinkedHashSet and LinkedHashMap Java 并发编程 > 线程机制、线程通信、J.U.C组件、JMM、线程安全、锁优化 Java I/O 磁盘...
Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 10、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap...
基于java tcp socket通信的拆包和装包源码 java-interview javac.exe&java.exe&javadoc.exe&PATH&CLASSPATH ...源码分析(集合&框架) 运行时数据区域 内存溢出 垃圾回收 垃圾收集器 类加载的过程 ComboBox(下拉列表框)
Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...
java内核源码 Java指南针 基础核心 基础知识 反射 泛型 动态代理 JDK8新特性 集合容器 多线程与并发 Spring SpringMVC SpringBoot Mybatis 数据结构与算法 入门基础 基础数据结构 数组&链表 数组&链表进阶 栈 队列 ...