java --HashTable学习
?今天在家无事,闲来看看JDK源码,就从HashTable看起了.
?
键值都不能为空。
为了能从hashtable中存储或者获取值，作为key的对象必须实现hashCode和equals方法。
一个hashtable实例有两个参数会影响它的效率：
?? 1、initial Capacity? (初始容量) 默认11
?? 2、load facotr （加载因子）:是对哈希表在其容量自动增加之前可以达到多满的一个尺度 默认0.75f
二、变量
(1)Entry[] table:the hash table data
(2)int count:the total number of entries in the hash table.
(3)threshold: the table is rehashed when its size exceeds this threshold.
? threshold=(int)(capacity * loadFactor).
(4)float loadFactor
(5)int modCount=0 :The mumber of times this Hashtable has been structurally modified.
三、方法
（1）构造方法中：
? 初始化initialCapacity
? 初始化loadFactor
? 初始化table=new Entry[initialCapacity]
? 初始化 threshold=(int)(capacity * loadFactor).
（2） public synchronized int size():返回count的值
（3） public synchronized boolean isEmpty() ：count是0返回true,否则返回false.
?(4)
?
public synchronized boolean contains(Object value) { if (value == null) { throw new NullPointerException(); } //数组，数组中的每一个元素又是一个单向链表(Entry:HashTable的内部类) Entry tab[] = table; for (int i = tab.length ; i-- > 0 ;) { for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) { if (e.value.equals(value)) { return true; } } } return false; }?
（5）第一步：得到当前key的hashCode
???? 第二步：通过hashCode得到在数组中的位置index
???? 第三步：根据index得到单向链表，从表头开始查找，是否存在当前元素。
public synchronized V get(Object key) { Entry tab[] = table; //得到hash值，通过hash值找到在数据中的位置，再在对应的单向链表中对应的值。 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; 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; }?
（6）增加数组的容量，重新计算hashCode，重新进行存储,大致分为以下几步：
? 第一步：增加容量至：oldCapacity * 2 + 1
? 第二步：循环数组，循环每个数组元素对应的单向链表，从头开始，重新计算hashCode，重新进行存储,
protected void rehash() { int oldCapacity = table.length; Entry[] oldMap = table; int newCapacity = oldCapacity * 2 + 1; Entry[] newMap = new Entry[newCapacity]; modCount++; threshold = (int)(newCapacity * loadFactor); table = newMap; for (int i = oldCapacity ; i-- > 0 ;) { for (Entry<K,V> old = oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = newMap[index]; newMap[index] = e; } } }?
(7) put方法，大致分为三步：
? 第一步：确保value不为空
? 第二步：循环数据，进一步循环链表，确保此key在当前hashTable中不存在，如果存在，则更换为新值。
? 第三步：modCount+1，如果当前的count >= threshold，则调用rehash()方法扩充数据容量，重新计算hashCode，重新进行存储。
? 第四步：在单向链表的表头插入当前entry.
?
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; 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++; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. Entry<K,V> e = tab[index]; tab[index] = new Entry<K,V>(hash, key, value, e); count++; return null; }?
总结：1、hashTable是线程安全的，键值不能为空。
????? 2、第一层存储结构是一个数组，数组中的每个元素又是一个单向链表。
????? 3、插入时，通过key的hashCode得到数组中存储位置，在单向链表的表头插入。
????? 4、插入时要检查当前数据中的元素个数，是否大于等于threshold，如果大于等于threshold，则会调用rehash()方法，建立一个新的数组，其大小为oldCapacity * 2 + 1,然后把旧的数组中的每个元素取出来，重新计算hashCode、在数组中的位置、在链表中的位置。
????? 5、因为threshold=初始容量*加载因子，所以rehash方法的调用与初始容量、加载因子有很大的关系，而rehash方法是hashtable中最费时间的方法，这就是为什么都说
hashtable实例的初始容量、加载因子最影响他的效率。
????? 6、默认加载因子(0.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间。
????? 7、初始容量主要控制空间消耗与执行 rehash 操作所需要的时间损耗之间的平衡。如果初始容量大于 Hashtable 所包含的最大条目数除以加载因子，即最大条目<初始容量
*加载因子，则永远 不会发生 rehash 操作。但是，将初始容量设置太高可能会浪费空间。