从源码看hashmap与hashtable区别
先看看hashmap与hashtable中的数据结构
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next;//存储冲突中链表下一个元素 final int hash;//依靠hash来索引map
从构造器看看两者不同
hashmap默认初始化容量为16;当使用非默认构造器时,其初始容量并非为所设置的容量initialCapacity,而是使用capacity,这里对初始容量做了个优化,保证初始容量为2的倍数,可以自己研究下原因。
还有在使用构造器初始化的时候最终hashmap都会调到init();
/** * Initialization hook for subclasses. This method is called * in all constructors and pseudo-constructors (clone, readObject) * after HashMap has been initialized but before any entries have * been inserted. (In the absence of this method, readObject would * require explicit knowledge of subclasses.) */ void init() { }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }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)(capacity * loadFactor); table = new Entry[capacity]; init(); }
hashtable默认初始化容量为11,并且需要调用Hashtable(int initialCapacity, float loadFactor);
public Hashtable() {this(11, 0.75f); } public Hashtable(int initialCapacity, float loadFactor) {if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load: "+loadFactor); if (initialCapacity==0) initialCapacity = 1;this.loadFactor = loadFactor;table = new Entry[initialCapacity];threshold = (int)(initialCapacity * loadFactor); }
看完初始化我们看下起最主要的不同方法PUT;
hashmap中,支持key和value都为空的情况,使用的hash为重新计算后的hash值,使用计算位置的方式也不一样 h & (length-1);当hashmap中的容量超过临界值时是将容量扩大为原来的1倍2 * table.length;
hashtable(同步)中当key为空的时候就直接报空指针,hash使用的是类自身的hashcode方法,计算位置使用的(hash & 0x7FFFFFFF) % tab.length;当hashtable中的容量超过临界值时是将容量扩大为oldCapacity * 2 + 1;
还可以看下两者在重新分配空间时候的做法。
public V put(K key, V value) { //处理key为空的特殊情况 if (key == null) return putForNullKey(value); //使用key的hashcode再hash int hash = hash(key.hashCode()); //i为放在hashmap中的位置 int i = indexFor(hash, table.length); //当相同位置有多个值时候,循环查找。 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果key为一样则返回原来的旧值,把新值插入到原key中 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //把对应的新map添加到i位置中 addEntry(hash, key, value, i); return null; }static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); } void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];//把每个冲突节点的旧链表放入Entry的next中 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) //如果map中内容超出threshold则将容量扩大1倍 resize(2 * table.length); } void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //构造新的map空间 Entry[] newTable = new Entry[newCapacity]; //将原有map中内容重新hash到新的位置 transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { //释放原有table在内存中的位置 src[j] = null; //如果当前节点里面有多个值,需要对每个值重新分配位置 do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
public synchronized V put(K key, V value) {// Make sure the value is not nullif (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; } 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; }} }
其他都有的方法基本类似
参考
http://blog.csdn.net/romans1981/archive/2005/03/07/313232.aspx
http://tieba.baidu.com/f?kz=890094718