Java集合框架——HashTable源码1.7详解

一、HashTable

1.特点

 键值都不能为空(否则会抛异常)
 key不能重复
 元素插入无序

2. 常用方法介绍

• synchronized int size() //元素总个数
• synchronized boolean isEmpty() //判断hashTable是否为空
• synchronizedboolean contains(Object value) //判断是否包含value值
• synchronized boolean containsKey(Object key) //判断是否包含key键
• synchronized V get(Object key) //通过key来进行获取值
• synchronized V put(K key, V value) //添加元素
• synchronized V remove(Object key) //删除元素

3.JDK1.7源码分析

• 继承关系
  继承Dictionary，实现了Map，cloneable和Serializable（序列化）

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, 
Cloneable, java.io.Serializable

• 底层数据结构
  数组+链表

• 基本属性和默认值

 transient Entry<K,V>[] table;//Entry类型的数组table
 int count;//记录容量
 int threshold; //扩容阈值
 float loadFactor;//加载因子
 transient int modCount = 0;//版本号
 数组默认大小11
 默认加载因子0.75

• 构造函数（4个）

1.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);
        initHashSeedAsNeeded(initialCapacity);
    }
 -  public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
 -  public Hashtable() {
        this(11, 0.75f);
    }
 -  public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

• 增长方式
  2+table.length+1 2倍 的数组的长度+1的 方式扩容
  int newCapacity = (oldCapacity << 1) + 1;

• put（）方法研究

  public synchronized V put(K key, V value) {
       //判断value是否为null，若为null，抛出空指针异常
        if (value == null) {
            throw new NullPointerException();
        }
        Entry tab[] = table;
		//key不能为null，key为null也会抛出空指针异常
		//通过key进行哈希，来获取到key该存储的索引位置
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length; //通过key的哈希，找到存储位置
        //对索引位置的链表进行遍历，获取key是否存在（key存在条件，hash相等且通过key.equals判断相等）
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
        modCount++;
        //扩容考虑  （Entry节点个数大于阈值）进行扩容，
        if (count >= threshold) { 
            rehash();
            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        // Creates the new entry.
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }

源码解析put（）方法：

 1.判断value是否为null，若为null，抛出空指针异常
 2.通过key进行哈希，来获取到key该存储的索引位置
 3.对索引位置的链表进行遍历，获取key是否存在
       （key存在的条件：hash相等且通过key.equals判断相等）。
 4.在存在key的情况下，将value值进行更新，且直接返回
 5.key不存在则进行新节点插入逻辑。
  5.1 扩容考虑：count>threshold（Entry节点个数大于阈值）进行扩容，
  5.2 新容量的大小:2*table.length+1
  5.3 将原来哈希表的所有元素进行重哈希到新的哈希表中
  5.4 更新插入的key的新位置
  5.5 找到新节点位置，创建Entry实体，通过头插法插入

4. hashTable保证线程安全原理：

hashTable在方法中添加Syncnized关键字，该关键字是一个互斥锁。目的是同一时刻只能有一个线程对资源进行访问
在hashMap中，对put，get等一般方法添加Syncnized关键字，修饰的是类对象，该对象调用put操作，即为该对象添加了一个
hashTable对象添加了一个互斥锁，同时只能有一个线程访问hashtable，从而保证添加元素不会出现异常。
底层操作系统提供的数组机制：从用户切换到内核态运行，当前的线程被阻塞住。