集合——HashTable

Hashtable

  • 线程安全
  • 键/值不可为null
  • 无序
  • 已被淘汰掉

实现

public class test_01 {
    public static void main(String[] args) throws IOException {
        /*
            初始化数组大小为11,数组加载因子0.75f
            public Hashtable() {
              this(11, 0.75f);
            }
        */
        Hashtable map = new Hashtable();
        //添加key-value
        map.put(1,1);
        map.put("",1);
        map.put(1,"");
        map.put(2,2);
        System.out.println(map);
    }
}
  • map.put(k,v);
    public synchronized V put(K key, V value) {
        // value为null 抛出异常
        if (value == null) {
            throw new NullPointerException();
        }
    <span class="hljs-comment">// Makes sure the key is not already in the hashtable.
    Entry&lt;?,?&gt; tab[] = table;
    <span class="hljs-comment">//获取hash值
    <span class="hljs-keyword">int hash = key.hashCode();
    <span class="hljs-comment">//根据hash值计算index下标
    <span class="hljs-keyword">int index = (hash &amp; <span class="hljs-number">0x7FFFFFFF) % tab.length;
    @SuppressWarnings(<span class="hljs-string">"unchecked")
    <span class="hljs-comment">//获取当前entry对象
    Entry&lt;K,V&gt; entry = (Entry&lt;K,V&gt;)tab[index];
    <span class="hljs-comment">//循环当前链表
    <span class="hljs-keyword">for(; entry != <span class="hljs-literal">null ; entry = entry.next) {
        <span class="hljs-comment">//判断hash值和key是否已经存在,如果存在,替换value
        <span class="hljs-keyword">if ((entry.hash == hash) &amp;&amp; entry.key.<span class="hljs-keyword">equals(key)) {
            V old = entry.<span class="hljs-keyword">value;
            entry.<span class="hljs-keyword">value = <span class="hljs-keyword">value;
            <span class="hljs-keyword">return old;
        }
    }
    <span class="hljs-comment">//如果下标中不存在节点,添加一个新的节点
    addEntry(hash, key, <span class="hljs-keyword">value, index);
    <span class="hljs-keyword">return <span class="hljs-literal">null;
}</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></code></pre>
  • addEntry(hash, key, value, index);
    private void addEntry(int hash, K key, V value, int index) {
        //操作数+1
        modCount++;
        Entry<?,?> tab[] = table;
        //如果存储的数据达到阀值
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            //刷新表
            rehash();
        tab = table;
        <span class="hljs-comment">//计算hash值
        hash = key.hashCode();
        <span class="hljs-comment">//获取下标
        index = (hash &amp; <span class="hljs-number">0x7FFFFFFF) % tab.length;
    }

    <span class="hljs-comment">// 创建新的entry对象
    @SuppressWarnings(<span class="hljs-string">"unchecked")
    Entry&lt;K,V&gt; e = (Entry&lt;K,V&gt;) tab[index];
    <span class="hljs-comment">//添加节点
    tab[index] = <span class="hljs-keyword">new Entry&lt;&gt;(hash, key, <span class="hljs-keyword">value, e);
    <span class="hljs-comment">//数据量+1
    count++;
}</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></code></pre>
  • rehash();
    protected void rehash() {
        //获取当前数组长度
        int oldCapacity = table.length;
        //获取当前数组
        Entry<?,?>[] oldMap = table;
    <span class="hljs-comment">// 扩容 -&gt; 大小为 (length * 2 + 1)
    <span class="hljs-keyword">int newCapacity = (oldCapacity &lt;&lt; <span class="hljs-number">1) + <span class="hljs-number">1;
    <span class="hljs-comment">//判断扩容后的大小是否超出最大数组长度
    <span class="hljs-keyword">if (newCapacity - MAX_ARRAY_SIZE &gt; <span class="hljs-number">0) {
        <span class="hljs-comment">//如果扩容前的数组长度 = 最大数组长度 , 结束
        <span class="hljs-keyword">if (oldCapacity == MAX_ARRAY_SIZE)
            <span class="hljs-comment">// Keep running with MAX_ARRAY_SIZE buckets
            <span class="hljs-keyword">return;
        <span class="hljs-comment">//否则最大数组长度就为扩容后的长度
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry&lt;?,?&gt;[] newMap = <span class="hljs-keyword">new Entry&lt;?,?&gt;[newCapacity];
    <span class="hljs-comment">//操作数 + 1
    modCount++;
    <span class="hljs-comment">//扩容临界点 = min[(扩容后的长度 * 0.75),(最大数组长度 + 1)]
    threshold = (<span class="hljs-keyword">int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + <span class="hljs-number">1);
    <span class="hljs-comment">//数组 = 扩容后的数组
    table = newMap;
    <span class="hljs-comment">//将原数组的数据 赋予新的数组
    <span class="hljs-keyword">for (<span class="hljs-keyword">int i = oldCapacity ; i-- &gt; <span class="hljs-number">0 ;) {
        <span class="hljs-comment">//循环原数组
        <span class="hljs-keyword">for (Entry&lt;K,V&gt; old = (Entry&lt;K,V&gt;)oldMap[i] ; old != <span class="hljs-literal">null ; ) {
            <span class="hljs-comment">//获取原数组的节点
            Entry&lt;K,V&gt; e = old;
            <span class="hljs-comment">//old节点 = old节点的下一个节点
            old = old.next;<span class="hljs-literal">null
            <span class="hljs-comment">//按扩容后的数组大小重新计算当前节点的下标
            <span class="hljs-keyword">int index = (e.hash &amp; <span class="hljs-number">0x7FFFFFFF) % newCapacity;
            <span class="hljs-comment">//原数组当前节点下一个节点 = 新的下标节点
            e.next = (Entry&lt;K,V&gt;)newMap[index];
            <span class="hljs-comment">//计算的新的下标的节点 = 原数组下标节点
            newMap[index] = e;
        }
    }
}</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></code></pre>

END

上一篇:深入吃透HashMap原理


下一篇:java集合浅谈——Map之TreeMap