HashTable源码1.7详解

女爷i 2021-09-28 12:30 245阅读 0赞

## 一、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实体，通过头插法插入

*  **get（）方法研究**

public synchronized V get(Object key) { 
            Entry tab[] = table;
            //通过key进行哈希，哈希到相应的位置
            int hash = hash(key);
            int index = (hash & 0x7FFFFFFF) % tab.length;
            //遍历当前索引位置节点，判断哈希以及key值是否相等，找到则直接返回，未找到则返回null
            for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 
                if ((e.hash == hash) && e.key.equals(key)) { 
                    return e.value;
                }
            }
            return null;
        }

*  **remove（）方法研究**

public synchronized V remove(Object key) { 
            Entry tab[] = table;
            //通过key哈希到相对应的索引位置
            int hash = hash(key);
            int index = (hash & 0x7FFFFFFF) % tab.length;
            //对该索引位置的链表进行遍历。找到和key相等的Entry实体，并进行删除。
            for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 
                if ((e.hash == hash) && e.key.equals(key)) { 
                    modCount++;
                    if (prev != null) {    //头结点
                        prev.next = e.next;
                    } else { 
                        tab[index] = e.next;
                    }
                    count--;
                    V oldValue = e.value;//返回
                    e.value = null;
                    return oldValue;
                }
            }
            return null;
        }

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

hashTable在方法中添加Syncnized关键字，该关键字是一个互斥锁。目的是同一时刻只能有一个线程对资源进行访问  
在hashMap中，对put，get等一般方法添加Syncnized关键字，修饰的是类对象，该对象调用put操作，即为该对象添加了一个互斥锁，同时只能有一个线程访问hashtable，从而保证添加元素不会出现异常。