HashMap和HashTable底层原理以及常见面试题
1.hashmap vs hashtable
1.1.首先说下 hashmap 的原理。
hashmap 的数据结构
/** the table, resized as necessary. length must always be a power of two. **/ transient entry[] table; static class entry<k,v> implements map.entry<k,v>{ final k key; v value; entry<k,v> next; final int hash; ... }
hashmap存储函数的实现put(k key, v value)
根据下面put方法的源代码可以看出,当程序试图将一个key-value对放入hashmap中时
- 1.程序首先计算该key的hashcode()值
- 2.然后对该哈希码值进行再哈希
- 3.然后把哈希值和(数组长度-1)进行按位与操作,得到存储的数组下标
- 4.如果该位置处设有链表节点,那么就直接把包含<key,value>的节点放入该位置。如果该位置有结点,就对链表进行遍历,看是否有hash,key和要放入的节点相同的节点,如果有的话,就替换该节点的value值,如果没有相同的话,就创建节点放入值,并把该节点插入到链表表头(头插法)。
public v put(k key, v value) { //hashmap允许存放null键和null值。 //当key为nu11时, 调用putfornullkey方法,将valve放置在数组第一个位置。 if (key = null) return putfornullkey(value); //根据key的keycode重新计算hash值。 int hash = hash(key .hashcode()); //搜索指定hash值在对应table中的索 int i = indexfor(hash, table . length); //如果i索引处的entry不为null,通过循环不断遍历e元素的下一个元素。 for (entry<k,v> e = table[i]; e != null;e = e.next) { object k; if (e.hash == hash && ((k == e.key) == key || key. equals(k))) { v oldvalue = e.value; e.value = value; e.recordaccess(this); return oldvalue; } } //如果读引处的entry为null,表明此处还没有entry omodcount++; //将key、 value添加到索引处。 addentry(hash, key, value, i); return null; }
void addentry(int hash, k key, v value, int bucketindex) { //获取指定bucketindex 索引处的entry entry<k,v> e = table[bucketindex]; //将新创健的entry 放入bucketindex索引处,并让新的entry 指向原来的entry table[bucketindex] = new entry<k,v>(hash, key, value, e); //如果hap中的key-value对的数里超过了极限 if (size++ >= threshold) //把table对象的长度扩充到原理的2倍 resize(2*table.length); }
二倍扩容
void resize(int newcapacity) { entry[] oldtable = table; int oldcapacity = oldtable.length; if (oldcapacity == maximum_capacity) { threshold = integer.max_value; return; } entry[] newtable = new entry[newcapacity]; transfer(newtable, inithashseedasneeded(newcapacity)); table = newtable; threshold = (int)math.min(newcapacity * loadfactor, maximum_capacity + 1); }
void transfer(entry[] newtable, boolean rehash) { int newcapacity = newtable.length; for (entry<k,v> e : table) { while(null != e) { entry<k,v> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexfor(e.hash, newcapacity); e.next = newtable[i]; newtable[i] = e; e = next; } } }
static int indexfor(int h, int length) { // assert integer.bitcount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }
static int hash(int h){ h ^ =(h>>>20)^ (h>>>12); return h ^ (h>>>7) ^ (h>>>4); }
扩展:为何数组的长度是2的n次方呢?
1.这个方法非常巧妙,它通过h & (table.length-1)来得到该对象的保存位,而hashmap底层数组的长度总是2的n次方,2^n -1得到的二进制数的每个位上的值都为1,那么与全部为1的一一个数进行与操作,速度会大大提升。
2.当length总是2的n次方时,h& (length-1)运 算等价王对length取模,也就是h%length,但是&比%县有更高的效率。
3.当数组长度为2的n次幂的时候,不同的key算得的index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰擁的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。
hashmap读取函数的实现get
public v get(object key) { if (key = null) return getfornullkey(); int hash ”hash(key.hashcode()); for (entry<k,v> e = table[indexfor(hash, table. length)]; e!=null; e = e.next) { 0bject k; if (e.hash=hash && ((k=e.key)==key ii key.equals(k)){ return e.value; } return null; }
hashmap的get方法1. 是首先通过key的两次hash后的值与数组的长度-1进行与操作,定位到数组的某个位置,2. 然后对该列的链表进行遍历,一般情况下,hashmap的这种查找速度是非常快的,hash 值相同的元(o就会造成链表中数据很多,而链表中的数据查找是通过应历所有链表中的元素进行的,这可能会影响到查找速度,找到即返回。特别注意:当返回为null时,你不能判断是没有找到指定元素,还是在hashmap中存着一一个value为null的元素,因为hashmap允许value为null.
hashmap的扩容机制:
当hashmap中的结点个数超过数组大小loadeactor*(加载因子)时,就会进行数组扩容,loadfactor的默认值为0.75.世就是说,默认情况下,数组大小为16,那么当hashmap电结点个数超过160.75=12的时候,就把数组的大小和展为216=32,即扩大一倍,然后重新计算每个元素在数组中的位置,并放进去,而这是一个非常消耗性能的操作。
多线程下hashmap出现的问题:
1.多线程put操作后,get操作导致死循环导致cpu100%的现象。主要是多线程同时put时,如果同时触发了rehash操作,会导政扩客后的hashmap中的链表中出现循环节点进而使得后面get的时候,会死循环。
2.多线程put操作,导致元素丢失,也是发生在个线程对hashmap 扩容时。
2.hashtable的原理。
它的原理和hashmap基本一致。
3.hashmap和hashtable的区别。
1.hashtable 是线程安全的,方法是synchronized 的,适合在多线程环境中使用,效率稍低: hashmap不是线程安全的,方法不是synchronized的,效率稍高,适合在单线程环境下使用,所以在多线程场合下使用的话,需要手动同步hashmap,collctions. synchronizedmap()。
ps:hashtable的效率比较低的原因?
在线程竞争激烈的情况下hashtable的效率非常低下。因为当一个线程访间hashtable的同步方法时,访问其他同步方法的线程就可能会进入阻嘉或者轮训状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈改率越低.
2.hashmap的key和value都可以为null值,hashtable 的key和value都不允许l null值。
3.hashmap中数组的默认大小是16,而且一定是2的倍数,扩容后的数組长度是之前数组长度的2倍。hashtable中数组默认大小是11.扩容后的数组长度是之前数组长度的2倍+1。
4.哈希直的使用不同。
而hashmap重新计算hash值,面且用&代替求模:
int hash = hash(key.hashcode0); int i= indexfor(hash, table.length); static int hash(objectx) { int h = x.hashcode(); h += ~(h<<9);h^= (h>>> 14); h+=(h<< 4); h ^= (h>>> 10); returm h; }
static int indexfor(int h, int length) { return h & (length-1); //hashmap的表长永远是2^n。 }
hashtable直接使用对象的hashcode值:
int hash = key.hashcode(); //注意区分2者的hash值!! int index = (hash & 0x7fffffff) % tab.length;
4.判断是否含有某个键
在hashmap中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为null,当get()方法返回null值时,既可以表示hashmap中没有该键,也可以表示该键所对应的值为null。因此,在hashmap中不能用get()方法来判断hashmap中是否存在某个键,而应该用containskey()方法来判析。hashtable的键值都不能为null,所以可以用get()方 法来判断是否含有某个键。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接
上一篇: 如何使用php等比例缩放图片
下一篇: java IO 文件操作方法总结