HashMap和HashTable底层原理以及常见面试题

发布时间:2020-09-03 18:37:35 作者:qq_43193797
来源:脚本之家 阅读:142

1.HashMap VS HashTable

1.1.首先说下 HashMap 的原理。

HashMap和HashTable底层原理以及常见面试题

HashMap和HashTable底层原理以及常见面试题

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中时

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()方 法来判断是否含有某个键。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对亿速云的支持。如果你想了解更多相关内容请查看下面相关链接

推荐阅读:
  1. HashMap和HashTable的区别是什么?
  2. HashMap和HashTable的区别以及常见面试题是什么

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

hashmap hashtable 见面

上一篇:使用C++中string实现任意长度的正小数、整数之间加减法方法实例

下一篇:Android sqlite设置主键自增长的方法教程

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》