package study;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class better {
public static void main(String[] args){
Map<String, String> map=new HashMap<String,String>();
map.put(“201901”,“chen”);
map.put(“201902”, “huang”);
map.put(“201903”, “zhang”);
Set keys=map.keySet();
for (String key : keys) {
String value=map.get(key);
System.out.println(key+"—"+value);
}
}
}

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

   private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

这段代码我大致是这么理解的,首先传递一个key过来,判断这个key是否存在,如果key为null,会走getForNullKey方法,getForNullKey进来之后会继续判断他的长度是否为0,如果为0的情况那么会反回空到控制台, 否者会获取table[0]上面的entry,然后会返回entry上面key为null的value到控制台;  

 final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

这段代码大致意思是,如果key不等于null,会根据这个key的哈希值,再到table数组里面找到对应的下标,获取entry;下面的e = e.next;我理解的意思是如果发生了哈希碰撞,那么一个位置可能会存在多个entry,那么多个entry的哈希值肯定是相同.然后自定义了一个Object k 变量;下面先把entry.key赋值给了k;再与传递过来的key进行的对比,如果相等的话就会返回entry;返回的entry从新回到了get()方法中,然后就可以通过这个entry.getValue()获取到他的value值返回到控制台了.

1、hashmap如何根据key找到value？

• 首先新建一个Node用于接收查询出来的Node节点

• hash（key）计算其hash码，并传入到getNode（）方法中 ，根据hash码和对应的key找到对应的节点

public V get(Object key) {

Node<K,V> e;

return (e = getNode(hash(key), key)) == null ? null : e.value;

}

• 我们先看Node， 可知这是一个实现Map.Entry的内部类

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

• 这是其中的一些方法，总结：Node是一个节点，为Key，Value形式。

• 然后我们来看getNode（）

• TODO 红黑树中如何查找

final Node<K,V> getNode(int hash, Object key) {

Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //新建一个Node类型链表数组，新建一个first

if ((tab = table) != null && (n = tab.length) > 0 &&   // tab 指向hash表，n为hash表的长度，first为桶中（链表数组）的第一个节点

(first = tab[(n - 1) & hash]) != null) { //当hash表中不为空并且头一个节点也不是null的时候

    if ( first.hash == hash && // always check first node 

    ((k = first.key) == key || (key != null && key.equals(k)) ) ) //如果头结点的hash码等于要找的hash码，并且对一个的key也是相等的话，就直接返回头节点

    return first;

    if ((e = first.next) != null) { //头节点下一个不是null

    if (first instanceof TreeNode) //如果是红黑树存储，就去红黑树里面找

        return ((TreeNode<K,V>)first).getTreeNode(hash, key);

    // 不是红黑树存储的话

    do { //遍历hash表，直到找到与对应结点的hash码值和对应key值相等的为止，并返回

        if (e.hash == hash &&

        ((k = e.key) == key || (key != null && key.equals(k))))

        return e;    

    } while ((e = e.next) != null);

    }

}

return null;

}

总结：

• 首先根据要查找的key计算出对应的哈希码

• 然后通过哈希码找到对应哈希表中桶中的地址

• 然后判断桶是链表结构还是红黑树结构

  • 普通链表直接遍历链表查找即可

  • 红黑树TODO