Java map和golang map的一些点

亦凉 2023-07-04 08:46 7阅读 0赞

### Java map和golang map的一些点 ###

*  hash函数
 *   *  Java
     *  golang
 *  内存存储模型：
 *   *  Java
     *   *  ConcurrentHashMap
         *   *  JDK7的分段锁思想
             *  JDK8的红黑树
     *  golang

背景：Java 1.8.40  
Golang 1.13.5

# hash函数 #

## Java ##

哈希函数代码如下：

static final int hash(Object key) { 
            int h;
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
       }

计算key对应的index是这样的：

p = tab[i = (n - 1) & hash]

对于hash函数，首先计算key对应的hash值。hash值是int类型，也就是4个字节，32位。然后将hashcode右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，然后得到最后的hash码。

然后依据hashmap的底层数组长度n(一定是2的次幂)，用n-1正好做一个低位掩码，然后 & hash码，得到最后的index。

那么这个时候问题就来了，为什么要将hashcode的低16位和高16位异或呢？因为如果hashmap的底层数组长度n比较小，我们只取最后几位，就算散列值分布再松散，只取最后几位，碰撞也会很严重。所以这里加入了一种“扰动函数” 的机制：比如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70]  
这里通过混合高16位和低16的信息(异或操作)，增大了随机性。

## golang ##

参考另一篇博客：[Golang map实践以及实现原理][Golang map][https://louyuting.blog.csdn.net/article/details/99699350\#hash\_200][Golang map]

# 内存存储模型： #

## Java ##

### ConcurrentHashMap ###

Java8以后，ConcurrentHashMap 和 HashMap的结构非常类似，基础结构都是 数组 + 链表(或红黑树)。这里重点描述ConcurrentHashMap。

主要对比下JDK7和JDK8两个版本之间ConcurrentHashMap的升级：

#### JDK7的分段锁思想 ####

JDK7 的分段锁是将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 1]  
从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

好处：写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。

坏处：这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长

#### JDK8的红黑树 ####

JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作。

JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。

Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样，不过保证线程安全性。

在JDK8中ConcurrentHashMap的结构，由于引入了红黑树，使得ConcurrentHashMap的实现非常复杂，我们都知道，红黑树是一种性能非常好的二叉查找树，其查找性能为O（logN），但是其实现过程也非常复杂。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 2]  
总结：  
从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

1.  数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
2.  保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。(这里可以看出JDK已经将Synchronized性能优化到极致了)
3.  锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
4.  链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
5.  查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

## golang ##

这里只列出一张模型图，具体可参考另一篇博客：[Golang map实践以及实现原理][Golang map 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200209181529933.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE=,size_16,color_FFFFFF,t_70
[Golang map]: https://louyuting.blog.csdn.net/article/details/99699350#hash_200
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200211223432303.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200211223640309.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE=,size_16,color_FFFFFF,t_70
[Golang map 1]: https://louyuting.blog.csdn.net/article/details/99699350
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200209182103506.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE=,size_16,color_FFFFFF,t_70