HashMap了解一下

今天跟着Java3y的博客&＃xff08;http://www.zhongfucheng.bitcron.com/post/shou-ji/pcduan-wen-zhang-dao-hang&＃xff09;看了一下map接口以及其下子类的代码&＃xff0c;水平有限&＃xff0c;看的晕晕乎乎的&＃xff0c;有的看不懂的地方暂时跳过了&＃xff0c;先把理解的地方记录一下&＃xff0c;好记性不如烂笔头头头头头。

依然盗图预警&＃xff0c;本博客仅用于记录和学习&＃xff0c;如有侵犯&＃xff0c;请联系我。

HashMap不走心的介绍

•  首先就是继承关系&＃xff1a;HashMap继承AbstractMap类同时实现Map接口
• 然后要理解一下hashmap的结构&＃xff0c;hashmap底层结构是散列表&＃43;红黑树&＃xff08;红黑树的理解可以参考其他的优质博文&＃xff1a;https://blog.csdn.net/chen_zhang_yu/article/details/52415077&＃xff09;&＃xff0c;至于散列表的实现&＃xff0c;hashmap是采用数组&＃43;链表的方式&＃xff0c;其中数组中的每个元素也就是平常说的桶&＃xff0c;而使用链表主要是为了解决哈希冲突的问题。&＃xff08;大概结构如下图所示&＃xff09;

• 下面来看一下HashMap的属性&＃xff1a;

• 然后是HashMap的构造方法&＃xff0c;HashMap有四个构造函数&＃xff0c;值得注意的是&＃xff0c;即使在构造函数中指定了initcapacity&＃xff0c;初始后的容量也不一定就是所指定的值。而是会返回一个大于指定值的且最接近的2的整数次幂。

• put方法&＃xff0c;以及put方法调用的putVal方法&＃xff0c;在putVal方法中&＃xff0c;初始时会调用resize方法初始化&＃xff0c;当插入元素后会如果size大于阈值的大小&＃xff0c;也需要调用resize方法进行再散列&＃xff0c;但是。。e..这个方法目前对我来说看着比较困难&＃xff0c;先总览一下&＃xff0c;随后再补充吧。

• get方法和remove方法&＃xff0c;两者的逻辑差不多&＃xff0c;以get方法为例&＃xff0c;get中调用的是getNode方法&＃xff0c;getNode方法中首先要保证key的哈希值是在散列表上的&＃xff0c;然后看是否在桶上&＃xff0c;如果在桶上则直接返回&＃xff0c;否则利用链表或者红黑树进行搜索并返回&＃xff08;删除&＃xff09;

hashmap补充

 问题1&＃xff1a;hashmap容量为什么是2的幂次

　　以下答案摘自&＃xff08;https://blog.csdn.net/dam454450872/article/details/80376661&＃xff09;

1. 首先length为2的整数次幂的话&＃xff0c;h&(length-1)就相当于对length取模&＃xff0c;这样便保证了散列的均匀&＃xff0c;同时也提升了效率&＃xff1b;&＃xff08;参考putVal方法中的使用&＃xff09;
2. 若length为偶数&＃xff0c;则最后一位为0&＃xff0c;减去1后&＃xff0c;最后一位一定为1&＃xff0c;此时与h做位与运算&＃xff0c;可能为奇数&＃xff0c;也可能为偶数。可以反过来想对比一下&＃xff0c;如果length为奇数&＃xff0c;减一后最后 一位为0&＃xff0c;与h做位与后&＃xff0c;最后一位为0&＃xff0c;一定为偶数&＃xff0c;这样不能保证散列的均匀性

问题2&＃xff1a;hashmap什么时候扩容

　　以下答案摘自&＃xff08;https://blog.csdn.net/u011328417/article/details/80728571&＃xff09;

1. 我们都知道hashmap的阈值为容量×装载因子。当元素个数大于阈值时就会触发一次扩容
2. hashmap中定义了TREEIFY_THRESHOLD默认值为8&＃xff0c;即当桶内链表的长度大于8时&＃xff0c;为了保证效率&＃xff0c;会转化为红黑树结构&＃xff0c;但是红黑树是治标不治本的&＃xff0c;即只能解决查找效率问题&＃xff0c;不能解决冲突问题。另外&＃xff0c;hashmap还定义了一个MIN_TREEIFY_CAPACITY默认值为64&＃xff0c;当桶中的bin被树化时最小的hash表容量。也就是说为当桶数组元素大于 64&＃xff0c;且桶内链表长度大于8时才将桶内链表转化为树形结构(这点反映在由链表向树形转化的方法treeifyBin中)。所以&＃xff0c;当桶内链表需要转化为红黑树前会先判断桶数组容量是否超过64&＃xff0c;若未超过则先进行桶容量扩容。

　　总结如下&＃xff1a;

　　　　当哈希表中的容量大于MIN_TREEIFY_CAPACITY时&＃xff0c;表中的桶才能进行树形化
　　　　否则桶内元素太多时会扩容&＃xff0c;而不是树形化
　　　　为了避免进行扩容、树形化选择的冲突&＃xff0c;MIN_TREEIFY_CAPACITY值不能小于 4 * TREEIFY_THRESHOLD

问题三&＃xff1a;hashmap的key为空值时怎么处理

hashmap中计算key的hash值时&＃xff0c;如果key为空则将其hash值直接赋值为0.

问题四&＃xff1a;hashmap和hashtable的区别

1、继承不同&＃xff0c;虽然二者都实现了map接口&＃xff0c;但hashmap继承abstractmap抽象类&＃xff0c;hashtable继承的是Dictionary类

2、Hashtable 中的方法是同步的&＃xff0c;而HashMap中的方法是非同步的。

3、Hashtable中&＃xff0c;key和value都不允许出现null值。

在HashMap中&＃xff0c;null可以作为键&＃xff0c;这样的键只有一个&＃xff1b;可以有一个或多个键所对应的值为null。当get()方法返回null值时&＃xff0c;即可以表示 HashMap中没有该键&＃xff0c;也可以表示该键所对应的值为null。因此&＃xff0c;在HashMap中不能由get()方法来判断HashMap中是否存在某个键&＃xff0c; 而应该用containsKey()方法来判断。

4、遍历方式不同&＃xff0c;虽然二者都可使用Iterator&＃xff0c;但hashtable还使用了enumeration的方式。

5、hash值的使用不同&＃xff0c;hashtable直接使用hashcode。而hasahmap重新计算hash值

6、初始大小和扩容方式不同。hashmap中hash数组初始大小是16&＃xff0c;而且一定是2的倍数。hashtable中hash数组默认大小是11&＃xff0c;增加的方式是old*2&＃43;1

&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;

 ConcurrentHashMap介绍

concurrentHashMap是Java.util.concurrent 包下的方法&＃xff0c;它也继承了AbstractMap抽象类&＃xff0c;但是实现的是ConcurrentMap接口。

然后是concurrenthashmap中用到的cas算法思想和volatile关键字。以下解释摘自https://mp.weixin.qq.com/s?__biz&＃61;MzI4Njg5MDA5NA&＃61;&＃61;&mid&＃61;2247484161&idx&＃61;1&sn&＃61;6f52fb1f714f3ffd2f96a5ee4ebab146&chksm&＃61;ebd74200dca0cb16288db11f566cb53cafc580e08fe1c570e0200058e78676f527c014ffef41#rd

cas&＃xff08;compare and swap &＃xff09;是一种无锁算法&＃xff0c;他有三个参数

内存值v

旧的预期值A

要修改的新值B

当且仅当v&＃61;&＃61;A时&＃xff0c;将v修改为B&＃xff0c;否则什么都不做。当多个线程尝试使用cas同时更新一个变量时&＃xff0c;只有其中一个线程能更新变量的值&＃xff0c;而其他线程都失败&＃xff0c;失败的线程不会被挂起&＃xff0c;而是被告知在这次竞争中失败&＃xff0c;并可以再次尝试。

更多介绍参考&＃xff1a;https://www.cnblogs.com/jianzh5/p/6671230.html

cas的缺点&＃xff1a;https://blog.csdn.net/v123411739/article/details/79561458

volatile经典总结&＃xff1a;volatile仅仅用来保证该变量对所有线程的可见性&＃xff0c;但不保证原子性。

先将今天的体会总结一下&＃xff1a;

1、concurrenthashmap的底层也是红黑树&＃43;散列表&＃xff0c;这点和hashmap相同

2、concurrenthashmap不允许存null&＃xff08;key和value&＃xff09;&＃xff0c;hashtable也不允许为null&＃xff0c;但hashmap允许为null

3、hashtable是使用sychonized对方法进行同步&＃xff0c;效率低下&＃xff0c;而concurrenthashmap是通过部分加锁&＃43;CAS算法来实现线程安全的。

4、concurrenthashmap重写了Node内部类&＃xff0c;通过volatile修饰val和next指针来实现每次获取的都是最新设置的值。