HashMap详解(一)

HashMap 简介

1.Hash Map

Hash Map 是一个散列表，这个散列表是无序的，存储的数据是以键值对的形式存储，一个key，对应一个value。

{
    "user_name":"tom",
    "user_sexy":"man",
    "user_age":"18"
}

2.哈希表的映射

百度百科这么定义,散列表，是通过把key映射到表中的某一个位置，地址空间内就是value值。这个映射函数叫散列函数，存放记录的数组叫散列表。

    
      address = f(key) //"映射函数"

也就是说我们认知的hash map 的 key 对 value 实际上是key 对应一个唯一地址，这个地址存放着这个value

3.哈希冲突

同样因为映射的缘故，存在这么一种情况

 f(key1)= f(key2)

两个不同的key值指向了同一个address，这个就是哈希冲突
HashMap 对于这种冲突的解决方式采用了 数组+链表+红黑树的方式。

源码如下：

 /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;
/**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

/**
     * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
     * extends Node) so can be used as extension of either regular or
     * linked node.
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
  }
    ...
}

有冲突就以链表的形式(next 不为null)，没有冲突就是一个数组形式 (next 为null)

4.效率问题

再从上面也可以看出一个问题，因为数据存储的方式不仅限于数组，所以当发生哈希冲突的时候，查询效率和不发生冲突有比较大的区别，一个在于next不为null时需要遍历一遍链表，而为null时不需要遍历，仅需要根据hashcode查一遍node数组就好了，红黑树他们说也有利于提升效率，具体怎样等我研究下。