源码分析第一期---Hashmap与Hashtable

• • HashMap源码分析
  • • 结构分析
    • Dbug 调试
    • HashTable基本使用介绍

一个HashMap集合是由table数组组成的，其中的链表节点存放在HashMap$Node中。

跳转到HashMap方法中去：
执行构造器，初始化加载因子：loadFactor 默认为0.75

 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

执行put方法：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

hash算法的底层实现逻辑

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

putVal的底层代码，主要实现扩容，和添加数据

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //这里先判段，如果底层的table数组为null，或者length长度为0，就进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
        //这里的resize就是扩容函数
            n = (tab = resize()).length;
        //取出hash值对应的table的索引位置的node，如果为null，就直接把加入的k-v，创建			 一个node，加入位置即可。
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            //如果table的索引位置的key的哈希值相同（表示key与加进来的key是同一个对象），或者是equals返回为真（就是key对应的内容相同）。
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
            //如果找到的节点后面是链表，就要循环比较
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                    //如果链表遍历完没有找到相同value 的值，就直接加在链表最后面
                        p.next = newNode(hash, key, value, null);
                        //当链表的数量大于8的时候就要变化成红黑树来存放值
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果循环的过程中有hash值相同或者是值相同，就替换原来的值
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
            //替换值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

树化（由链表抓换为红黑树）的条件:
大家看源码可以知道，如果table为null，或者大小还没到64，暂时不树化而是先扩容。

final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        //如果table为null，或者大小还没到64，暂时不树化而是先扩容。
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode hd = null, tl = null;
            do {
                TreeNode p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

• 存放元素是键值对：k-v
• 存放的键值都不能为null，否则会抛出空指针异常
• Hashtable是线程安全的(synchronized )，hashmap是线程不安全的

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

简单说一线Hashtable的扩容机制

• 底层有数组 Hashtable$Entry[] 初始化大小是11；
• 临界值threahold = 8；（8 = 11*0.75）
• 扩容机制，按照 int newCapacity = (oldCapacity << 1) + 1;的大小进行扩容。