总述:通过一定的算法,将key的hashcode转换成数组的index;将key,value,hash等信息保存在数组对应的index位置上.
问题:
1.某些key的hashcode相同
2.hashcode不同,但一定算法后映射到数组的index相同
这个就是常说的hashcode冲突问题.
1.HashMap涉及的数据结构
Entry[] ;
//Entry数组:存储HashMap元素的地方.
//Entry
//1.封装了key;value;
//2.本身是一个单向链表;包含hash值;next;指针;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
/**
* Create new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
....
}
2.存储的过程:
通过hashcode得到index后.存储的不仅仅是该元素的key,value,hash.还有指向下一个Entry的引用.如果出现了hashcode冲突问题.则新建一个Entry;将该Entry的nex指针指向已存在的Entry.
public V put(K key, V value) {
K k = maskNull(key);
int hash = hash(k); //算hash
int i = indexFor(hash, table.length); //取对应的index
//该index对应的Entry可能不是一个Entry,而是一个Entry链.
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) { //已存在,则更新值.
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, k, value, i); //该位置还空;或者位置不空,但已有Entry(hashcode冲突)
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//取到当前位置上的Entry,可能是null
Entry<K,V> e = table[bucketIndex];
//创建新Entry,next指向已存在的
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);//扩容.
}
3.取值的过程
还是hash-index-Entry的过程.不是直接return该index上Entry;而要检查Entry链上真正对应的那个
public V get(Object key) {
Object k = maskNull(key);
int hash = hash(k); //取hash
int i = indexFor(hash, table.length);//取index
//取回来的是一个Entry链
Entry<K,V> e = table[i];
//遍历
while (true) {
if (e == null)
return null;
if (e.hash == hash && eq(k, e.key)) //真正要get的那个
return e.value;
e = e.next; //指针后移到下一个Entry
}
}
算个复习吧.没看过的看看.笔试面试很常见.
分享到:
相关推荐
HashMap的用法---马克-to-win java视频的详细描述与介绍
看完这篇 HashMap,和面试官扯皮就没问题了 - HashMap 概述 - HashMap 和 HashTable 的区别 - 相同点 - 不同点 - HashMap 和 HashSet 的区别 - HashMap 底层结构 - AbstractMap 类 - Map 接口 - 重要内部类...
hashmap的原理啊思想。
20-集合框架020-HashMap-1080P 高清-AVC20
5.HashMap是怎么解决哈希冲突的? 6.什么是哈希? 7.什么是哈希冲突? 8.HashMap的数据结构? 9.JDK1.8新增红黑树? 10.能否使用任何类作为 Map 的 key? 11.为什么HashMap中String、Integer这样的包装类适合作为K?...
HashMap源码分析系列-第四弹:HashMap多线程解决方案.docx
JAVA之hashmap源码分析 Mobile-Dev-Analysis Analysis of android or java 红岩网校工作站移动开发部学员分组学习 为了让大家学的更加坚固,采取小组学习的方式帮助大家学习,同时在学习研究的过程中需要不断的做...
java代码-使用java解决手写hashMap的源代码 ——学习参考资料:仅用于个人学习使用!
hashmap源码 Excellent-Blog-share Welcome to share excellent blogs . 当你的能力还驾驭不了你的目标时,就应该沉下心来历练 当你的才华还撑不起你的野心时,那你就应该静下心来学习 #目录 ###附录 java系列 java8...
hashmap的get流程 - 副本
哈希映射线程测试使用 Maven 构建和运行 mvn exec:java
Java 实例 - HashMap遍历源代码-详细教程.zip
hashmap源码 java-notes 算法 数据结构 设计模式 基础 集合 ConcurrentHashMap IO 并发 [Java 并发]( 并发.md) AQS 源码 JVM web 基础 [NGINX 简介](./docs/nginx/NGINX 简介.md) 框架 Spring [观察 Spring bean ...
java7 hashmap源码 learn-java 学习java源码 集合 并发集合 队列 线程 面试
易语言HashMap类源码
hashmap源码 spring-boot 1.总览 spring ioc 实现方式JNDI DI是EJB容器的注入 spring aop 事务简化 spring mvc 2.入门 创建springboot 项目 打成jar包,解压 META-INF目录下 MANIFEST.MF org.spring...
hashmap源码 learning-record - 学习轨迹记录 10月1号 7月18号 基础算法:反转单向链表 7月16号 7月11号 7月9号 复习 : HashTable和HashMap的区别详解 LeetCode 27. 删除元素(Remove Element) 7月8号 7月5号 复习...
hashmap源码 Java-# JAVA面试知识梳理 0. java大纲 一、java基础 1.基础 1.1 JDK & JRE 区别 JDK:Java Development Kit 的简称,Java 开发工具包,提供了 Java 的开发环境和运行环境。 JRE:Java Runtime ...
hashmap源码 Note-For-Java 记录一下java学习过程的重要知识点 1.在java中如果被除数或者除数有一个为浮点类型,0或者0.0是可以用作除数的,结果得正负无穷;取余操作亦是如此。 2.java在7.0之后switch语句case后面...