美文网首页
HashMap详解(一)

HashMap详解(一)

作者: 用心感受世界 | 来源:发表于2018-10-22 16:55 被阅读0次

    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数组就好了,红黑树他们说也有利于提升效率,具体怎样等我研究下。

    相关文章

      网友评论

          本文标题:HashMap详解(一)

          本文链接:https://www.haomeiwen.com/subject/kqlqwftx.html