Mlog6:哈希表

2017-8-1

[1] 概念

哈希表(散列表)，根据键直接访问在内存存储位置的数据结构。
若关键字为 k ,则其值存放到 f(k) 的存储位置上。其中， f(k) 称为散列函数，存放记录的数组称为散列表。

哈希是 key/value的集合

[2] HashTable

HashTable--一个散列表，它存储的内容是键值对

1. 源码

//HashTable继承于Dictionary类，实现Map、Cloneable、 java.io.Serializable接口
public class Hashtable<K,V>  
    extends Dictionary<K,V>  
    implements Map<K,V>, Cloneable, java.io.Serializable{}

2. 成员变量

(1) table是一个 Entry[] 数组类型，而 Entry（在 HashMap 中有讲解过）实际上就是一个单向链表。
哈希表的"key-value键值对"都是存储在Entry数组中的。
(2) count 是 Hashtable 的大小，它是 Hashtable 保存的键值对的数量。
(3) threshold 是 Hashtable 的阈值，用于判断是否需要调整 Hashtable 的容量。threshold 的值="容量*加载因子"。
(4) loadFactor 就是加载因子。
(5) modCount 是用来实现 fail-fast 机制的。

3. PUT 方法
4. GET方法
5. 遍历

Enumeration<String> en1 = table.keys();
    while(en1.hasMoreElements()) {
    en1.nextElement();
}

[3] HashMap

HashMap--一个“链表散列”的数据结构，即数组和链表的结合体

1. 源码

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
}

2. PUT方法
3. GET方法
4. 遍历

　Map map = new HashMap();
　　Iterator iter = map.entrySet().iterator();
　　while (iter.hasNext()) {
　　Map.Entry entry = (Map.Entry) iter.next();
　　Object key = entry.getKey();
　　Object val = entry.getValue();
　　}

[3] 差异

1、HashMap是非线程安全的，HashTable是线程安全的。
2、HashMap的键和值都允许有null值存在，而HashTable则不行。
3、因为线程安全的问题，HashMap效率比HashTable的要高

[4] HashTable和ConcurrentHashMap的比较

如我开篇所说一样，ConcurrentHashMap是线程安全的HashMap的实现。同样是线程安全的类，它与HashTable在同步方面有什么不同呢？
之前我们说，synchronized关键字加锁的原理，其实是对对象加锁，不论你是在方法前加synchronized还是语句块前加，锁住的都是对象整体，但是ConcurrentHashMap的同步机制和这个不同，它不是加synchronized关键字，而是基于lock操作的，这样的目的是保证同步的时候，锁住的不是整个对象。事实上，ConcurrentHashMap可以满足concurrentLevel个线程并发无阻塞的操作集合对象。