HashMap中的几个重要变量

默认初始容量,必须是2的n次方

static final int DEFAULT_INITIAL_CAPACITY = 16;

最大容量，当通过构造方法传入的容量比它还大时，就用这个最大容量，必须是2的n次方

static final int MAXIMUM_CAPACITY = 1 << 30;

默认负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

用来存储键值对，可以看到键值对都是存储在Entry中的

transient Entry<K,V>[] table;

//capacity * load factor,超过这个数就会进行再哈希
int threshold;

HashMap中的元素是用名为table的Entry数组来保存的，默认大小是16

• capacity:数组的容量
• load_factor:负载因子
• threshold：实际能承载的容量，等于上面两个相乘，当size大于threshold时，就会进行rehash
  

jdk7中在面对key为String的时候采用了区别对待，会有alternative hashing，但是这个在jdk8中已经被删除了

存储结构

Entry是一个链表结构，不仅包含key和value，还有可以指向下一个的next

static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 int hash;

 /**
  * Creates new entry.
  */
 Entry(int h, K k, V v, Entry<K,V> n) {
  value = v;
  next = n;
  key = k;
  hash = h;
 }
 ...

put方法

public V put(K key, V value) {
 if (key == null)
  return putForNullKey(value);
 int hash = hash(key);
 int i = indexFor(hash, table.length);
 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;
  }
 }

 modCount++;
 addEntry(hash, key, value, i);
 return null;
 }

首先通过hash方法对hashcode进行处理：

final int hash(Object k) {
 int h = 0;
 h ^= k.hashCode();

 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }

可以看到只是在key的hashcode值上做了一些处理，通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标：

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

这个方法其实相当于对table.length取模。

当需要插入的key为null时，调用putForNullKey方法处理：

 private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null) {
  V oldValue = e.value;
  e.value = value;
  e.recordAccess(this);
  return oldValue;
  }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
 }

putForNullKey方法只从table[0]这个位置开始遍历，因为key为null只放在table中的第一个位置，下标为0，在遍历中如果发现已经有key为null了，则替换新value，返回旧value，结束；如果还没有key为null，调用addEntry方法增加一个Entry:

void addEntry(int hash, K key, V value, int bucketIndex) {
 if ((size >= threshold) && (null != table[bucketIndex])) {
  resize(2 * table.length);
  hash = (null != key) ? hash(key) : 0;
  bucketIndex = indexFor(hash, table.length);
 }

 createEntry(hash, key, value, bucketIndex);
 }

可以看到jdk7中resize的条件已经发生改变了，只有当 size>=threshold并且 table中的那个槽中已经有Entry时，才会发生resize。即有可能虽然size>=threshold，但是必须等到每个槽都至少有一个Entry时，才会扩容。还有注意每次resize都会扩大一倍容量

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++;
 }

最后看createEntry，它先保存这个桶中的第一个Entry，创建新的Entry放入第一个位置，将原来的Entry接在后面。这里采用的是头插法插入元素。

get方法

其实get方法和put方法如出一辙，怎么放的怎么拿

public V get(Object key) {
 if (key == null)
  return getForNullKey();
 Entry<K,V> entry = getEntry(key);

 return null == entry ? null : entry.getValue();
 }

key为null时，还是去table[0]去取：

private V getForNullKey() {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null)
  return e.value;
 }
 return null;
 }

否则调用getEntry方法：

final Entry<K,V> getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key);
 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;
 }

这个方法也是通过key的hashcode计算出它应该所在的下标，再遍历这个下标的Entry链，如果key的内存地址相等（即同一个引用）或者equals相等，则说明找到了

hash的原则

A、等幂性。不管执行多少次获取Hash值的操作，只要对象不变，那么Hash值是固定的。如果第一次取跟第N次取不一样，那就用起来很麻烦.

B、对等性。若两个对象equal方法返回为true，则其hash值也应该是一样的。举例说明：若你将objA作为key存入HashMap中，然后new了一个objB。在你看来objB和objA是一个东西（因为他们equal），但是使用objB到hashMap中却取不出来东西。

C、互异性。若两个对象equal方法返回为false，hash值有可能相同，但最好是不同的，这个不是必须的，只是这样做会提高hash类操作的性能（碰撞几率低）。

解决hash碰撞的方法：

• 开放地址法
• 链地址法

hashmap采用的就是链地址法，这种方法好处是无堆积现象，但是next指针会占用额外空间

和jdk8中的HashMap区别

在jdk8中，仍然会根据key.hashCode()计算出hash值，再通过这个hash值去定位这个key，但是不同的是，当发生冲突时，会采用链表和红黑树两种方法去处理，当结点个数较少时用链表（用Node存储），个数较多时用红黑树（用TreeNode存储），同时结点也不叫Entry了，而是分成了Node和TreeNode。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。jdk8中的HashMap中定义了一个变量TREEIFY_THRESHOLD，当节点个数>= TREEIFY_THRESHOLD - 1时，HashMap将采用红黑树存储

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。

# jdk1.7  # hashmap  # jdk  # 1.7  # hashmap源码  # HashMap红黑树入门(实现一个简单的红黑树)  # 解析ConcurrentHashMap: 红黑树的代理类(TreeBin)  # JDK8中的HashMap初始化和扩容机制详解  # 为什么JDK8中HashMap依然会死循环  # HashMap在JDK7与JDK8中的实现过程解析  # 遍历  # 可以看到  # 的是  # 红黑  # 是一个  # 链表  # 就会  # 有可能  # 才会  # 就用  # 最大容量  # 时用  # 键值  # 计算出  # 都是  # 几个  # 还没有  # 会有  # 成了  # 放在 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 如何快速搭建高效简练网站？  javascript中闭包概念与用法深入理解  如何在橙子建站上传落地页？操作指南详解  Laravel怎么实现搜索功能_Laravel使用Eloquent实现模糊查询与多条件搜索【实例】  个人摄影网站制作流程,摄影爱好者都去什么网站？  南京网站制作费用,南京远驱官方网站？  在centOS 7安装mysql 5.7的详细教程  如何在橙子建站中快速调整背景颜色？  国美网站制作流程,国美电器蒸汽鍋怎么用官方网站？  Laravel如何实现事件和监听器？（Event & Listener实战）  html如何与html链接_实现多个HTML页面互相链接【互相】  成都网站制作公司哪家好,四川省职工服务网是做什么用？  免费制作统计图的网站有哪些,如何看待现如今年轻人买房难的情况？  专业商城网站制作公司有哪些,pi商城官网是哪个？  教你用AI将一段旋律扩展成一首完整的曲子  Laravel如何使用Facades（门面）及其工作原理_Laravel门面模式与底层机制  lovemo网页版地址 lovemo官网手机登录  网站制作怎么样才能赚钱,用自己的电脑做服务器架设网站有什么利弊，能赚钱吗？  百度输入法ai面板怎么关 百度输入法ai面板隐藏技巧  如何快速上传建站程序避免常见错误？  Laravel API资源类怎么用_Laravel API Resource数据转换  香港服务器建站指南：免备案优势与SEO优化技巧全解析  laravel怎么用DB facade执行原生SQL查询_laravel DB facade原生SQL执行方法  高端建站如何打造兼具美学与转化的品牌官网？  Bootstrap整体框架之CSS12栅格系统  Laravel广播系统如何实现实时通信_Laravel Reverb与WebSockets实战教程  Laravel Blade模板引擎语法_Laravel Blade布局继承用法  高性价比服务器租赁——企业级配置与24小时运维服务  Laravel中间件如何使用_Laravel自定义中间件实现权限控制  为什么php本地部署后css不生效_静态资源加载失败修复技巧【技巧】  Laravel如何监控和管理失败的队列任务_Laravel失败任务处理与监控  如何有效防御Web建站篡改攻击？  详解Huffman编码算法之Java实现  手机软键盘弹出时影响布局的解决方法  香港服务器网站搭建教程-电商部署、配置优化与安全稳定指南  Laravel如何实现数据库事务？（DB Facade示例）  Laravel如何清理系统缓存命令_Laravel清除路由配置及视图缓存的方法【总结】  javascript基本数据类型及类型检测常用方法小结  Win11任务栏卡死怎么办 Windows11任务栏无反应解决方法【教程】  百度输入法全感官ai怎么关 百度输入法全感官皮肤关闭  微博html5版本怎么弄发语音微博_语音录制入口及时长限制操作【教程】  Laravel怎么实现模型属性的自动加密  Laravel如何处理异常和错误？（Handler示例）  网站制作大概多少钱一个,做一个平台网站大概多少钱？  LinuxCD持续部署教程_自动发布与回滚机制  深圳网站制作平台,深圳市做网站好的公司有哪些？  ,网页ppt怎么弄成自己的ppt？  非常酷的网站设计制作软件,酷培ai教育官方网站？  如何用腾讯建站主机快速创建免费网站？  Python面向对象测试方法_mock解析【教程】