JAVA源码学习之集合-Hashtable

JAVA源码学习之集合-Hashtable 类的描述

public class Hashtable
extends Dictionary
implements Map, Cloneable, Serializable

此类实现了一个哈希表，它将键映射到值。任何非空对象都可以用作键或值。

要成功地从哈希表存储和检索对象，用作键的对象必须实现hashCode方法和equals方法。

哈希表的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的存储桶数，初始容量只是创建哈希表时的容量。请注意，哈希表是open：在“哈希冲突”的情况下，单个bucket存储多个条目，必须按顺序搜索这些条目。负载因子是在自动增加哈希表容量之前允许哈希表达到的满度的度量。初始容量和负载系数参数只是对实现的提示。关于何时以及是否调用rehash方法的确切细节取决于实现。

通常，默认负载系数（0.75）提供了时间和空间成本之间的良好折衷。较高的值会减少空间开销，但会增加查找条目的时间开销（这反映在大多数哈希表 *** 作中，包括get和put）。

初始容量控制浪费的空间和重新灰化 *** 作的需要之间的折衷，这非常耗时。如果初始容量大于哈希表包含的最大条目数除以其负载因子，则不会发生重新缓存 *** 作。但是，将初始容量设置得过高可能会浪费空间。

如果要在哈希表中创建多个条目，那么创建具有足够大容量的哈希表可能会比让哈希表根据需要执行自动扩容以增长表更有效地插入条目。

本例创建一个数字哈希表。它使用数字的名称作为键：  Hashtable numbers
    Hashtable  numbers = new Hashtable();
   numbers.put("one", 1);
   numbers.put("two", 2);
   numbers.put("three", 3);

要检索数字，请使用以下代码：

 Integer n = numbers.get("two");
   if (n != null) {
     System.out.println("two = " + n);
   }

该类的所有“集合视图方法”返回的集合的迭代器方法返回的迭代器都是fail-fast:的：如果在迭代器创建后的任何时间，以迭代器自己的remove方法以外的任何方式修改哈希表的结构，迭代器将抛出ConcurrentModificationException。因此，在面对并发修改时，迭代器会快速、干净地失败，而不是在将来的不确定时间冒着任意、不确定行为的风险。哈希表的键和元素方法返回的枚举不是快速失败的。

请注意，无法保证迭代器的快速失效行为，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此，编写依赖于此异常的正确性的程序是错误的：迭代器的快速失败行为应该只用于检测bug。

从Java2平台v1开始。2，对该类进行了改造以实现Map接口，使其成为Java集合框架的成员。与新的集合实现不同，哈希表是同步的。如果不需要线程安全的实现，建议使用HashMap代替Hashtable。如果需要线程安全的高并发实现，则建议使用java。util。同时发生的ConcurrentHashMap代替Hashtable。

常量、变量、内部类

    
    private transient Entry[] table;

    
    private transient int count;

    
    private int threshold;

    
    private float loadFactor;

//节点对象
private static class Entry implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Entry next;

        protected Entry(int hash, K key, V value, Entry next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }

        @SuppressWarnings("unchecked")
        protected Object clone() {
            return new Entry<>(hash, key, value,
                                  (next==null ? null : (Entry) next.clone()));
        }

        // Map.Entry Ops

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;

            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
               (value==null ? e.getValue()==null : value.equals(e.getValue()));
        }

        public int hashCode() {
            return hash ^ Objects.hashCode(value);
        }

        public String toString() {
            return key.toString()+"="+value.toString();
        }
    }

构造方法

public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }


 public Hashtable() {
        this(11, 0.75f);
    }


   public Hashtable(Map t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t); //放到put
    }

通过上面可以看出，Hashtable默认容量是11， 默认扩展因子未0.75

put

 public synchronized V put(K key, V value) {
        //value不能为空
        if (value == null) { 
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry entry = (Entry)tab[index];
        //从key的hash值对应的index的位置向下循环遍历table
        for(; entry != null ; entry = entry.next) {
            //匹配，替换value然后返回oldValue
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

  //添加entru
  private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry tab[] = table;
        //如果当前节点数大于等于扩容边界值（因为当count=threshold时，+1比大于threshold）， 扩容
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        //将当前index位置的元素置为e.next 然后当前位置设置成为e, 头插
        Entry e = (Entry) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

protected void rehash() {
        int oldCapacity = table.length;
        Entry[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1; // 扩容2倍+1
        if (newCapacity - MAX_ARRAY_SIZE > 0) {  //和 Integer.MAX_VALUE - 8进行比较
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry[] newMap = new Entry[newCapacity];

        modCount++;
        //设置边界
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;

         //将旧table中的元素通过计算index放到新的table中
        for (int i = oldCapacity ; i-- > 0 ;) {
            //遍历链表
            for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
                Entry e = old;
                old = old.next;
                
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                 //将当前index位置的元素置为e.next 然后当前位置设置成为e, 头插
                e.next = (Entry)newMap[index];
                newMap[index] = e;
            }
        }
    }


  public synchronized void putAll(Map t) {
        for (Map.Entry e : t.entrySet())
            //调用的put方法
            put(e.getKey(), e.getValue());
    }

通过put我们发现HashTable的数据结构是数组+链表的形式

该图片copy至： java之HashTable - 夏攸 - 博客园 (cnblogs.com)

 然后hashtable的链表使用的是头插

get

  public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

remove

public synchronized V remove(Object key) {
        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry e = (Entry)tab[index];
        //遍历位置index处的链表，找到位置
        for(Entry prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++；
                if (prev != null) {  //e不是头节点
                    prev.next = e.next;
                } else {
                    //e是头节点，所以e.next作为头节点
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }

结论：

1.数据结构为数组+链表， 链表使用的头插

2. 相关方法使用了synchronized修饰，所以是线程安全的