登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›11.Java SDK源码分析系列笔记-Hashtable

11.Java SDK源码分析系列笔记-Hashtable

璋锌 2025-9-25 21:03:05
猛犸象科技工作室:网站开发，备案域名，渗透，服务器出租，DDOS/CC攻击，TG加粉引流
目录

  • 1. 是什么
  • 2. 如何使用
  • 3. 原理分析

    • 3.1. uml
    • 3.2. 构造方法
    • 3.3. put方法

      • 3.3.1. 使用synchronized加锁
      • 3.3.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
      • 3.3.3. 遍历链表直到找到相等的节点或者到末尾
      • 3.3.4. 没有找到，新建节点加入链表头部

        • 3.3.4.1. 扩容


    • 3.4. get方法

      • 3.4.1. 使用synchronized加锁
      • 3.4.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
      • 3.4.3. 遍历链表直到找到相等的节点或者到末尾

    • 3.5. remove方法

      • 3.5.1. 使用synchronized加锁
      • 3.5.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
      • 3.5.3. 遍历链表直到找到相等的节点或者到末尾，把value置为null

    • 3.6. containsKey方法

      • 3.6.1. 使用synchronized加锁
      • 3.6.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
      • 3.6.3. 遍历链表直到找到相等的节点或者到末尾



1. 是什么

线程安全的hashmap
2. 如何使用
  1. public class HashtableTest
  2. {
  3.     public static void main(String[] args) throws InterruptedException
  4.     {
  5.         Hashtable<Integer, Integer> map = new Hashtable<>();
  6.         Thread thread1 = new Thread(()->{
  7.             for (int i = 0; i < 100000; i++)
  8.             {
  9.                 map.put(i, i);
  10.             }
  11.         });
  13.         Thread thread2 = new Thread(()->{
  14.             for (int i = 100000; i < 200000; i++)
  15.             {
  16.                 map.put(i, i);
  17.             }
  18.         });
  20.         thread1.start();
  21.         thread2.start();
  22.         thread1.join();
  23.         thread2.join();
  24.         System.out.println(map);
  25.         System.out.println(map.size());
  26.         for (int i = 0; i < 200000; i++)
  27.         {
  28.             if (!map.contains(i))
  29.             {
  30.                 throw new RuntimeException("并发put有问题");//不会抛出异常说明并发put没问题
  31.             }
  32.             System.out.println(map.remove(i));
  33.         }
  34.     }
  35. }
复制代码
3. 原理分析

3.1. uml

1.png

可克隆，可序列化，实现了Map接口
3.2. 构造方法

使用链地址法（单链表）解决Hash冲突
初始化容量为11，默认的加载因子为0.75
  1. public class Hashtable<K,V>
  2.     extends Dictionary<K,V>
  3.     implements Map<K,V>, Cloneable, java.io.Serializable {
  4.    
  5.     //使用Entry数组实现
  6.     private transient Entry<?,?>[] table;
  8.     //map中实际元素的个数
  9.     private transient int count;
  11.     //以下两个决定了什么时候扩容
  12.     private int threshold;
  13.     private float loadFactor;
  15.     private transient int modCount = 0;
  17.     public Hashtable() {
  18.             //初始化容量为11，加载因子为0.75
  19.         this(11, 0.75f);
  20.     }
  22.     public Hashtable(int initialCapacity, float loadFactor) {
  23.         //检查参数合法
  24.         if (initialCapacity < 0)
  25.             throw new IllegalArgumentException("Illegal Capacity: "+
  26.                                                initialCapacity);
  27.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  28.             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  30.         if (initialCapacity==0)
  31.             initialCapacity = 1;
  32.         this.loadFactor = loadFactor;
  33.         //创建table数组
  34.         table = new Entry<?,?>[initialCapacity];
  35.         //threshold取int MAX_ARRAY_SIZE = Integer.MAX_VALUE  8和initialCapacity * loadFactor中的小者
  36.         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  37.     }
  38. }
复制代码
3.3.1. 使用synchronized加锁
  1. //加了synchronized
  2. public synchronized V put(K key, V value) {
  3.     // Make sure the value is not null
  4.     //与HashMap不同，这里value不能为null
  5.     if (value == null) {
  6.         throw new NullPointerException();
  7.     }
  9.     // Makes sure the key is not already in the hashtable.
  10.     Entry<?,?> tab[] = table;
  11.     int hash = key.hashCode();
  12.     //计算下标
  13.     int index = (hash & 0x7FFFFFFF) % tab.length;
  14.     @SuppressWarnings("unchecked")
  15.     Entry<K,V> entry = (Entry<K,V>)tab[index];
  16.     //遍历链表直到找到相等的节点或者到末尾
  17.     for(; entry != null ; entry = entry.next) {
  18.             //找到了，替换value
  19.         if ((entry.hash == hash) && entry.key.equals(key)) {
  20.             V old = entry.value;
  21.             entry.value = value;
  22.             return old;
  23.         }
  24.     }
  26.         //没有找到，新建节点加入链表
  27.     addEntry(hash, key, value, index);
  28.     return null;
  29. }
复制代码
3.3.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
  1. public synchronized V put(K key, V value) {
  2. //...
  3. }
复制代码
3.3.3. 遍历链表直到找到相等的节点或者到末尾
  1. Entry<?,?> tab[] = table;
  2. int hash = key.hashCode();
  3. //计算下标
  4. //计算index是通过对数组长度取模而不是使用与操作
  5. int index = (hash & 0x7FFFFFFF) % tab.length;
  6. @SuppressWarnings("unchecked")
  7. Entry<K,V> entry = (Entry<K,V>)tab[index];
复制代码
3.3.4. 没有找到，新建节点加入链表头部


  • addEntry方法
  1. //遍历链表直到找到相等的节点或者到末尾
  2. for(; entry != null ; entry = entry.next) {
  3.         //找到了，替换value
  4.     if ((entry.hash == hash) && entry.key.equals(key)) {
  5.         V old = entry.value;
  6.         entry.value = value;
  7.         return old;
  8.     }
  9. }
复制代码
3.3.4.1. 扩容


  • rehash方法
  1. private void addEntry(int hash, K key, V value, int index) {
  2.     modCount++;
  4.     Entry<?,?> tab[] = table;
  5.     //判断是否需要扩容
  6.     if (count >= threshold) {
  7.         // Rehash the table if the threshold is exceeded
  8.         rehash();
  10.         tab = table;
  11.         hash = key.hashCode();
  12.         index = (hash & 0x7FFFFFFF) % tab.length;
  13.     }
  15.     // Creates the new entry.
  16.     @SuppressWarnings("unchecked")
  17.     Entry<K,V> e = (Entry<K,V>) tab[index];
  18.     //新建节点并且直接放入数组相应位置
  19.     tab[index] = new Entry<>(hash, key, value, e);
  20.     count++;
  21. }
复制代码
3.4. get方法
  1. @SuppressWarnings("unchecked")
  2. protected void rehash() {
  3.     int oldCapacity = table.length;
  4.     Entry<?,?>[] oldMap = table;
  6.     // overflowconscious code
  7.     //新capacity=旧capacity*2+1
  8.     int newCapacity = (oldCapacity << 1) + 1;
  9.     //如果容量超过了MAX_ARRAY_SIZE（int MAX_ARRAY_SIZE = Integer.MAX_VALUE  8），那么以MAX_ARRAY_SIZE为准
  10.     if (newCapacity  MAX_ARRAY_SIZE > 0) {
  11.         if (oldCapacity == MAX_ARRAY_SIZE)
  12.             // Keep running with MAX_ARRAY_SIZE buckets
  13.             return;
  14.         newCapacity = MAX_ARRAY_SIZE;
  15.     }
  16.     //以新capacity创建新数组
  17.     Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
  19.     modCount++;
  20.     threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  21.     table = newMap;
  22.         //由后往前遍历entry数组
  23.     for (int i = oldCapacity ; i > 0 ;) {
  24.             //从头到尾遍历链表
  25.         for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
  26.                 //e表示此次要迁移的节点，old表示下一个要迁移的节点
  27.             Entry<K,V> e = old;
  28.             old = old.next;
  30.                         //计算e在新entry数组中的位置
  31.             int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  32.             //把e的next指向新entry数组中的位置（链表的头节点）
  33.             e.next = (Entry<K,V>)newMap[index];
  34.             //再把新entry数组中的位置赋值为e
  35.             //等于就是头插法
  36.             newMap[index] = e;
  37.         }
  38.     }
  39. }
复制代码
3.4.1. 使用synchronized加锁
  1. //加了synchronized
  2. public synchronized V get(Object key) {
  3.     Entry<?,?> tab[] = table;
  4.     int hash = key.hashCode();
  5.     //计算在那个链表中
  6.     int index = (hash & 0x7FFFFFFF) % tab.length;
  7.     //遍历链表找到相等的节点
  8.     for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
  9.         if ((e.hash == hash) && e.key.equals(key)) {
  10.             return (V)e.value;
  11.         }
  12.     }
  13.     return null;
  14. }
复制代码
3.4.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
  1. public synchronized V get(Object key) {
  2. }
复制代码
3.4.3. 遍历链表直到找到相等的节点或者到末尾
  1. Entry<?,?> tab[] = table;
  2. int hash = key.hashCode();
  3. //计算在那个链表中
  4. int index = (hash & 0x7FFFFFFF) % tab.length;
复制代码
3.5. remove方法

使用synchronized修饰
同get方法找到节点，删除的操作就是链表节点的删除操作
  1. //遍历链表找到相等的节点
  2. for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
  3.     if ((e.hash == hash) && e.key.equals(key)) {
  4.         return (V)e.value;
  5.     }
  6. }
复制代码
3.5.1. 使用synchronized加锁
  1. public synchronized V remove(Object key) {
  2.         Entry<?,?> tab[] = table;
  3.         int hash = key.hashCode();
  4.         int index = (hash & 0x7FFFFFFF) % tab.length;
  5.         @SuppressWarnings("unchecked")
  6.         Entry<K,V> e = (Entry<K,V>)tab[index];
  7.         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
  8.                 if ((e.hash == hash) && e.key.equals(key)) {
  9.                     modCount++;
  10.                     if (prev != null) {
  11.                             //不是头节点
  12.                         prev.next = e.next;
  13.                     } else {
  14.                             //头节点
  15.                         tab[index] = e.next;
  16.                     }
  17.                     count;
  18.                     //help GC
  19.                     V oldValue = e.value;
  20.                     e.value = null;
  21.                     return oldValue;
  22.                 }
  23.         }
  24.         return null;
  25. }
复制代码
3.5.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
  1. public synchronized V remove(Object key) {
  2. }
复制代码
3.5.3. 遍历链表直到找到相等的节点或者到末尾，把value置为null
  1. Entry<?,?> tab[] = table;
  2. int hash = key.hashCode();
  3. int index = (hash & 0x7FFFFFFF) % tab.length;
  4. @SuppressWarnings("unchecked")
  5. Entry<K,V> e = (Entry<K,V>)tab[index];
复制代码
3.6. containsKey方法
  1. @SuppressWarnings("unchecked")
  2. Entry<K,V> e = (Entry<K,V>)tab[index];
  3. for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
  4.         if ((e.hash == hash) && e.key.equals(key)) {
  5.             modCount++;
  6.             if (prev != null) {
  7.                     //不是头节点
  8.                 prev.next = e.next;
  9.             } else {
  10.                     //头节点
  11.                 tab[index] = e.next;
  12.             }
  13.             count;
  14.             //help GC
  15.             V oldValue = e.value;
  16.             e.value = null;
  17.             return oldValue;
  18.         }
  19. }
复制代码
3.6.1. 使用synchronized加锁
  1. //加了synchronized
  2. public synchronized boolean containsKey(Object key) {
  3.         //以下逻辑同get方法
  4.     Entry<?,?> tab[] = table;
  5.     int hash = key.hashCode();
  6.     int index = (hash & 0x7FFFFFFF) % tab.length;
  7.     for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
  8.         if ((e.hash == hash) && e.key.equals(key)) {
  9.             return true;
  10.         }
  11.     }
  12.     return false;
  13. }
复制代码
3.6.2. 计算key落在entry数组中的哪个位置【或者说哪个链表】
  1. public synchronized boolean containsKey(Object key) {
  2. }
复制代码
3.6.3. 遍历链表直到找到相等的节点或者到末尾
  1. Entry<?,?> tab[] = table;
  2. int hash = key.hashCode();
  3. int index = (hash & 0x7FFFFFFF) % tab.length;
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
JavaSDK源码分析系列

使用道具 举报

相关推荐
缑娅瑛
2025-10-15 11:51:16

举报

程序园永久vip申请，500美金$，无限下载程序园所有程序/软件/数据/等
这个好，看起来很实用
寨亳
2025-10-29 00:58:08

举报

程序园永久vip申请，500美金$，无限下载程序园所有程序/软件/数据/等
东西不错很实用谢谢分享
窝酴
3 天前

举报

程序园永久vip申请，500美金$，无限下载程序园所有程序/软件/数据/等
这个有用。
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
璋锌
3 天前

0

粉丝关注

23

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫