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

/**
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;
  ...
 }

• 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);
}

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;
}

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。
}

int hash = key.hashcode(); //注意区分2者的hash值!! int index = (hash & 0x7fffffff) % tab.length;