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 操作。但是，将初始容量设置太高可能会浪费空间。