首页天道酬勤hashmap和list区别,为什么要用hashmap

hashmap和list区别,为什么要用hashmap

张世龙 05-05 19:56 119次浏览

文章前言源代码分析继承关系的差异:HashMapHashtable是否支持键值null的差异: HashMapHashtable初始化和扩展方法的差异: HashtableHashMap计算hash值的差异33366

前言: HashMap和Hashtable是我们常用的两个Map的集合,Hashtable知道可以保证线程的安全,但其实他们的源代码实现上野有很多不同。 以下将讨论如何重写HashMap和Hashtable源代码。

提示:以下为本文正文内容,以下案例可供参考

源代码解析继承关系不同的: HashMap HashMap继承AbstractMap

public class HashMapK,V extends AbstractMapK,V implements MapK,v,Cloneable,serializable hashtable继承Dictionary

公共类hashtable k,V extends DictionaryK,V implements MapK,v,Cloneable,java.io.Serializable是否支持键值null HashmapHashasle只有一个这样的键。 对应于一个或多个键的值可以为空。

publicvput(kkey,V value ) returnputval ) hash ) key,key,value,false,true ); }finalvputval(inthash,K key,V value,boolean onlyIfAbsent,boolean evict ) { NodeK,V[] tab; NodeK,V p; int n,I; if () tab=table )==null||(n=tab.Length )=0) n=(tab=resize ) ).length; if () p=tab(I=(n-1 ) hash]] ) null (tab ) I )=new node (hash,key,value,null ); else { NodeK,V e; k; if(p.hash==hash ) (k=p.key )==key||(key!=nullkey.equals(k ) ) (e=p; elseif(pinstanceoftreenode ) e=(treenodek,v ) p ).puttreeval ) this,tab,hash,key,value ); else{for(intbincount=0; binCount () if ) (e=p.next ) null ) ) p.next=newnode ) hash,key,value,null ); if (bincount=tree ify _ threshold-1 )/-1for1STTreeifybin(tab,hash ); 布雷克; (if ) e.hash==hash((k=e.key )==key||(key!=nullkey.equals(k ) ) (break; p=e; }if(e!=null (//existingmappingforkeyvoldvalue=e.value; if (! olyifabsent|||old value==null (e.value

= value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } Hashtable

Hatable 不允许 null值(key 和 value 都不可以) key为 null 没有 hash() ,value 为 null 的时候报异常

public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { //value为null抛出NullPointerException 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; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; } private void addEntry(int hash, K key, V value, int index) { Entry<?,?> tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; modCount++; } 初始化和扩容的方式不同: Hashtable public Hashtable() { this(11, 0.75f);//初始容量为11}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]; // new 初始化数组 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);} HashMap

HshMap的初始化在上偏文章中做了详细介绍这里就好Hashtable()做比较就可以了
HashTable 在构造方法里面进行初始化,初始化大小为 11 每次扩容的时候变为原来的 2n+1 倍
HashMap调用默认构造是没有初始化的 在第一次 调用 put 方法的时候,在 resize() 里面进行初始化,初始化大小为 16, 每次扩容后,变为原来的 2倍

计算 hash 值的方法不同: HashTable 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; // 下标计算 @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null;} HashMap static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 计算得到}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // 这个方法前面有}

HashTable:直接调用 Object 的 hash() 函数,计算出来 hash 值,下标直接 数组长度取余得到
​ int hash = key.hashCode();
​ int index = (hash & 0x7FFFFFFF) % tab.length
Hash Map:首先 高位和低位异或得到 hash 值,然后 再和数组大小-1 做 与运算 得到下标
​ int hash = key.hashCode() ^ (h >>> 16);
int index = (n - 1) & hash;

线程安全: public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); }

HashTable的好多方法使用synchronized进行加锁操作保证了线程安全
HashMap 线程不安全

总结

1、继承的父类不一样

HashTable :继承 DictionaryHashMap:继承AbstractMap

2、线程安全

HashTable:线程安全HashMap:线程不安全

3、初始化的扩容不一样

HashTable:在构造方法里面初始化,初始化大小为 11,每次扩容 2n+1 倍HashMap:在 put 值的时候进行初始化,初始化大小为 16,每次扩容 2倍

4、计算下标的方法不同

HashTable:hash值 直接调用 Object 类的HashCode() 方法,计算下标直接对数组长度取余HashMap:hash值 是通过 高位和低位异或 得到,下标通过 数组长度 和 hash值进行与运算得到

5、键和值 的 null 取值不同

HashTable:键和值都不允许为 nullHashMap:键和值都可以为 null,只能有唯一的键值为 null,可以有多个值为 null
hashmap是什么,hashtable底层实现原理