黑马程序员技术交流社区

标题: 深入解析HashTable一 [打印本页]

---

作者: 小刀葛小伦    时间: 2019-8-8 17:53
标题: 深入解析HashTable一


一、HashTable的内部存储结构

HashTable和HashMap采用相同的存储机制，二者的实现基本一致，不同的是：

1、HashMap是非线程安全的，HashTable是线程安全的，内部的方法基本都是synchronized。

2、HashTable不允许有null值的存在。

在HashTable中调用put方法时，如果key为null，直接抛出NullPointerException。其它细微的差别还有，比如初始化Entry数组的大小等等，但基本思想和HashMap一样。

二、HashTable和ConcurrentHashMap的比较

ConcurrentHashMap是线程安全的HashMap的实现。同样是线程安全的类，它与HashTable在同步方面有什么不同呢？

synchronized关键字加锁的原理，其实是对对象加锁，不论你是在方法前加synchronized还是语句块前加，锁住的都是对象整体，但是ConcurrentHashMap的同步机制和这个不同，它不是加synchronized关键字，而是基于lock操作的，这样的目的是保证同步的时候，锁住的不是整个对象。事实上，ConcurrentHashMap可以满足concurrentLevel个线程并发无阻塞的操作集合对象。

1、构造方法

为了容易理解，我们先从构造函数说起。ConcurrentHashMap是基于一个叫Segment数组的，其实和Entry类似，如下：

[Java] 纯文本查看 复制代码

public ConcurrentHashMap()

  {

    this(16, 0.75F, 16);

  }

默认传入值16，调用下面的方法：

[AppleScript] 纯文本查看 复制代码

public ConcurrentHashMap(int paramInt1, float paramFloat, int paramInt2)

  {

    if ((paramFloat <= 0F) || (paramInt1 < 0) || (paramInt2 <= 0))

      throw new IllegalArgumentException();

 

    if (paramInt2 > 65536) {

      paramInt2 = 65536;

    }

 

    int i = 0;

    int j = 1;

    while (j < paramInt2) {

      ++i;

      j <<= 1;

    }

    this.segmentShift = (32 - i);

    this.segmentMask = (j - 1);

    this.segments = Segment.newArray(j);

 

    if (paramInt1 > 1073741824)

      paramInt1 = 1073741824;

    int k = paramInt1 / j;

    if (k * j < paramInt1)

      ++k;

    int l = 1;

    while (l < k)

      l <<= 1;

 

    for (int i1 = 0; i1 < this.segments.length; ++i1)

      this.segments[i1] = new Segment(l, paramFloat);

  }

你会发现比HashMap的构造函数多一个参数，paramInt1就是我们之前谈过的initialCapacity，就是数组的初始化大小，paramfloat为loadFactor（装载因子），而paramInt2则是我们所要说的concurrentLevel，这三个值分别被初始化为16,0.75,16，经过：

[Java] 纯文本查看 复制代码

while (j < paramInt2) {

      ++i;

      j <<= 1;

    }

后，j就是我们最终要开辟的数组的size值，当paramInt1为16时，计算出来的size值就是16.通过：

this.segments = Segment.newArray(j)后，我们看出了，最终稿创建的Segment数组的大小为16.最终创建Segment对象时：

[Java] 纯文本查看 复制代码

this.segments[i1] = new Segment(cap, paramFloat);

需要cap值，而cap值来源于：

[Java] 纯文本查看 复制代码

int k = paramInt1 / j;

    if (k * j < paramInt1)

      ++k;

    int cap = 1;

    while (cap < k)

      cap <<= 1;

组后创建大小为cap的数组。最后根据数组的大小及paramFloat的值算出了threshold的值：

this.threshold = (int)(paramArrayOfHashEntry.length * this.loadFactor)。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2