HashTable学习笔记

1、Hashtable简单介绍

  1. HashTable是线程安全的数据结构，多个线程可以共享一个HashTable

  2. HashTable的Key和Value都不允许为null

  3. HashTable底层用数组和链表进行实现

  4. HashTable默认容量为11，负载因子为0.75

  5. HashTable每次扩容大小为 *2+1

  6. HashTable的遍历通过Enumeration

  7. HashMap是通过”拉链法”实现的哈希表。它包括几个重要的成员变量： table, size, threshold, loadFactor, modCount。
    ①table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
    ②size是HashMap的大小，它是HashMap保存的键值对的数量。
    ③threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值=“容量*负载因子”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
    ④loadFactor就是负载因子。
    ⑤modCount是用来实现fail-fast机制的。

2、HashTable的四种构造函数

1、public Hashtable(int initialCapacity, float loadFactor)

  1. public Hashtable(int initialCapacity, float loadFactor) {
  2.     if (initialCapacity < 0)
  3.         throw new IllegalArgumentException("Illegal Capacity: "+
  4.                                            initialCapacity);
  5.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  6.         throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  8.     if (initialCapacity==0)
  9.         initialCapacity = 1;
  10.     this.loadFactor = loadFactor;
  11.     table = new Entry<?,?>[initialCapacity];
  12.     threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  13. }

指定初始容量，和负载因子

2、public Hashtable(int initialCapacity)

  1. public Hashtable(int initialCapacity) {
  2.     this(initialCapacity, 0.75f);
  3. }

指定初始化容量，使用默认的负载因子0.75

3、public Hashtable()

  1. public Hashtable() {
  2.     this(11, 0.75f);
  3. }

无参构造函数，使用默认容量11和默认的初始化影子0.75

4、public Hashtable(Map<? extends K, ? extends V> t)

  1. public Hashtable(Map<? extends K, ? extends V> t) {
  2.     this(Math.max(2*t.size(), 11), 0.75f);
  3.     putAll(t);
  4. }

创造一个包含Map的子类

3、HashTable的原理

简单来说，HashTable的原理和HashMap是一样的，HashMap是HashTable的轻量级实现

有关原理部分可以看我有关HashMap的笔记HashMap的学习笔记

4、HashTable几个方法详解

1、get方法

  1. public synchronized V get(Object key) {
  2.     Entry<?,?> tab[] = table;
  3.     int hash = key.hashCode();
  4.     int index = (hash & 0x7FFFFFFF) % tab.length;
  5.     for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
  6.         if ((e.hash == hash) && e.key.equals(key)) {
  7.             return (V)e.value;
  8.         }
  9.     }
  10.     return null;
  11. }

①HashTable的get方法是同步的，因为它加了锁

②我们可以看到它求数组下表的方式是(hash & 0x7FFFFFFF) % tab.length

0x7FFFFFFF是一个质数，这样可以保证(hash & 0x7FFFFFFF)进行于运算后出来一个正整数，不会产生数组下表的异常

③当找到数组下表后，就是常见的循环链表判断操作，直到找出这个数

2、put

  1. public synchronized V put(K key, V value) {
  2.     // Make sure the value is not null
  3.     if (value == null) {
  4.         throw new NullPointerException();
  5.     }
  7.     // Makes sure the key is not already in the hashtable.
  8.     Entry<?,?> tab[] = table;
  9.     int hash = key.hashCode();
  10.     int index = (hash & 0x7FFFFFFF) % tab.length;
  11.     @SuppressWarnings("unchecked")
  12.     Entry<K,V> entry = (Entry<K,V>)tab[index];
  13.     for(; entry != null ; entry = entry.next) {
  14.         if ((entry.hash == hash) && entry.key.equals(key)) {
  15.             V old = entry.value;
  16.             entry.value = value;
  17.             return old;
  18.         }
  19.     }
  21.     addEntry(hash, key, value, index);
  22.     return null;
  23. }

put方法也非常容易理解，主要就是判断了Key和Value不允许为空，然后同样使用拉链法

先计算hash确定位置，然后使用链表