Android HashTable

参考资料

一、HashTable

它和HashMap一样是一个散列链表，它的容器是一个数组，而每一个数组中的元素都是一个单向的链表。相对于HashMap来说，它是Map的一个同步的实现。它不支持空key的情况。

二、基本参数

DEFAULT_INITIAL_CAPACITY：默认容量
DEFAULT_LOAD_FACTOR：默认的负载因子,表示散列链表的使用度，数越大那么使用度越高。
entry：链表对象
table：链表的容器是一个数组
threshold：临界点，当达到这个临界点的时候进行扩容，它等于负载因子*容量大小

二、创建一个HashTable

1.如果容量是0的话会创建一个空的HashTable
2.如果不是0，会根据传入的容量计算一个n^2的合理容量大小的数组减小碰撞

    public Hashtable(int capacity) {
       
        if (capacity == 0) {
            @SuppressWarnings("unchecked")
            HashtableEntry<K, V>[] tab = (HashtableEntry<K, V>[]) EMPTY_TABLE;
            table = tab;
            threshold = -1; // Forces first put() to replace EMPTY_TABLE
            return;
        }

        if (capacity < MINIMUM_CAPACITY) {
            capacity = MINIMUM_CAPACITY;
        } else if (capacity > MAXIMUM_CAPACITY) {
            capacity = MAXIMUM_CAPACITY;
        } else {
            capacity = Collections.roundUpToPowerOfTwo(capacity);
        }
        makeTable(capacity);
    }

    private HashtableEntry<K, V>[] makeTable(int newCapacity) {
        @SuppressWarnings("unchecked") HashtableEntry<K, V>[] newTable
                = (HashtableEntry<K, V>[]) new HashtableEntry[newCapacity];
        table = newTable;
        threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
        return newTable;
    }

三、HashTable的函数接口

HashTable的重要函数都是同步方法

synchronized void                clear()
synchronized Object              clone()
             boolean             contains(Object value)
synchronized boolean             containsKey(Object key)
synchronized boolean             containsValue(Object value)
synchronized Enumeration<V>      elements()
synchronized Set<Entry<K, V>>    entrySet()
synchronized boolean             equals(Object object)
synchronized V                   get(Object key)
synchronized int                 hashCode()
synchronized boolean             isEmpty()
synchronized Set<K>              keySet()
synchronized Enumeration<K>      keys()
synchronized V                   put(K key, V value)
synchronized void                putAll(Map<? extends K, ? extends V> map)
synchronized V                   remove(Object key)

四、HashTable的插入

1.它是不支持key，value==null的
2.它会根据key的hash值以及数组的长度计算元素在数组中的位置，如果有一样的元素那么会覆盖之前的元素
3.如果容量已满的话那么会进行扩容
4.在数组的当前位置插入元素，如果该位置有元素，将新元素放在首位将并且next指向旧的元素形成链表
5.查询是获取当前index位置的entry，遍历entry是否有相同元素。

 public synchronized V put(K key, V value) {
        if (key == null) {
            throw new NullPointerException("key == null");
        } else if (value == null) {
            throw new NullPointerException("value == null");
        }
        int hash = Collections.secondaryHash(key);
        HashtableEntry<K, V>[] tab = table;
        int index = hash & (tab.length - 1);
        HashtableEntry<K, V> first = tab[index];
        for (HashtableEntry<K, V> e = first; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // No entry for key is present; create one
        modCount++;
        if (size++ > threshold) {
            rehash();  // Does nothing!!
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
            first = tab[index];
        }
        tab[index] = new HashtableEntry<K, V>(key, value, hash, first);
        return null;
    }

四、HashTable的查询

1.根据key的hash值和数组长度计算出元素在数组的index，遍历entry，查询符合条件的元素

   public synchronized V get(Object key) {
        int hash = Collections.secondaryHash(key);
        HashtableEntry<K, V>[] tab = table;
        for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }

五、HashTable的优劣

1.首先相对于HashMap它是线程安全的，可以在多线程共享数据
2.因为它的主要方法都加入了synchronized关键词，所以在单一线程上的性能不如HashMap