欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-12 10:57:14
...

一、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,从而保证添加元素不会出现异常。
底层操作系统提供的数组机制:从用户切换到内核态运行,当前的线程被阻塞住。

相关标签: HashTable