网站地图怎么做、/社会新闻最新消息

       闲聊的时候被突然问起，于是查了查资料，总结如下。

       由浅入深hashmap

       HashMap所在java集合的位置如下图所示

1 、大致介绍一下java的集合体系结构

       List Set Map是这个集合体系中最主要的三个接口。

       List、Set继承自Collection接口。

       Set不允许元素重复。HashSet和TreeSet是两个主要的实现类。

       List有序且允许元素重复。ArrayList、LinkedList和Vector是三个主要的实现类。

       Map也属于集合系统,但和Collection接口不同，AbstractMap实现了Map接口，HashMap继承AbstractMap。SortedMap继承Map接口，TreeMap继承SortedMap。从图中我们可知。

       Map是key对value的映射集合，其中key是一个集合，key不能重复，但是value可以重复。HashMap、TreeMap和HashTable是三个主要实现类。

       大概介绍了一下java的集合类，接下来主要介绍的是HashMap，HashMap在java集合类中的位置在图中能看到。

2、HashMap位置

      HashMap 继承了AbstractMap，AbstractMap实现了Map接口，LinkedHashMap继承了HashMap。

3、 什么时候使用HashMap？

      当你需要通过一个名字来获取数据的时候就可以用Map，并且这个名字（也就是key）是不重复的，且在添加和删除等情况下不需要线程安全，这时候我们就可以用HashMap。

      比如当把用户的信息存入list的时候，当你根据用户id查询某某学生名字时，可能需要遍历，这时候用Map，直接通过key来找到value就可以了。

      总之，需要键值对的时候，用map就可以了。

4 、HashMap使用code

       code见：https://github.com/summerxhf/j2ee-demo/blob/master/HashMap-demo/src/main/java/HashMapDemo.java

5、 HashMap概述

      HashMap 是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别不保证该顺序恒久不变。（我们可以运行demo中的方法，插入顺序和输出顺序并不是一个顺序。）

6、 HashMap数据结构

      在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用）。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

      一维数组

      链表

      所以HashMap结构如下图

      所以HashMap底层就是一个数组结构，数组中的每一项又是存放的链表的头结点。当新建一个HashMap的时候，就会初始化一个数组。

      当new一个HashMap，内部代码如下所示：

             对于任何一个数组，在初始化建立的时候，都会涉及到建立数组的大小，数组长度是否够用？能否自动扩充数组容量呢？这些问题。

      下面是初始化数组时的一下参数定义code

           /*** The defaultinitial capacity - MUST be a power of two.*/
static final int DEFAULT_INITIAL_CAPACITY = 16;// 默认初始容量为16，必须为2的幂/*** The maximumcapacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be apower of two <= 1<<30.*/
static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量为2的30次方/*** The loadfactor used when none specified in constructor.*/
static final floatDEFAULT_LOAD_FACTOR = 0.75f;// 默认加载因子0.75/*** The table,resized as necessary. Length MUST Always be a power oftwo.*/
transientEntry<K,V>[] table;// Entry数组，哈希表，长度必须为2的幂/*** The number ofkey-value mappings contained in this map.*/
transient int size;// 已存元素的个数/*** The next sizevalue at which to resize (capacity * load factor).* @serial*/
int threshold;// 下次扩容的临界值，size>=threshold就会扩容/*** The loadfactor for the hash table.** @serial*/
final float loadFactor;// 加载因子

       在newHashMap的时候，构造方法如下：

      我们常用的没有参数的构造方法，代码如下。

       //构造一个具有默认初始容量 (16)和默认加载因子 (0.75) 的空 HashMap。

    public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;threshold = (int)(DEFAULT_INITIAL_CAPACITY* DEFAULT_LOAD_FACTOR);table = new Entry[DEFAULT_INITIAL_CAPACITY];init();}

       table为Entry数组，怎么理解这个Entry？map为地图，Entry可以理解为地图中的各个节点，登记处。在new一个HashMap的时候，默认会初始化16个Entry，加载因子是，当数组中的个数超出了加载因子与当前容量的乘积时，就会通过调用rehash方法将容量翻倍。例如默认的扩容因子为0.75， 则扩充的临界值为16* 0.75 = 12， 也就是map中存放超过12个key value映射时，就会自动扩容。

7 、HashMap初始化之后

       new完一个HashMap后，进行put值，put的代码如下：

         //在此映射中关联指定值与指定键。如果该映射以前包含了一个该键的映射关系，则旧值被替换，并返回旧值。

 public V put(K key, V value) {// 如果key为null使用putForNullKey来获取if (key == null)return putForNullKey(value);// 使用hash函数预处理hashCodeint hash = hash(key.hashCode());// 获取对应的索引int i = indexFor(hash, table.length);// 得到对应的hash值的桶，如果这个桶不是，就通过next获取下一个桶for (Entry<K,V> e = table[i]; e != null;e = e.next) {Object k;// 如果hash相同并且key相同if (e.hash== hash && ((k = e.key) == key || key.equals(k))) {// 获取当前的valueV oldValue = e.value;// 将要存储的value存进去e.value = value;e.recordAccess(this);// 返回旧的valuereturn oldValue;}}modCount++;addEntry(hash, key, value, i);return null;}

    // key为null怎么放value

  private V putForNullKey(V value) {// 遍历table[0]的所有桶for (Entry<K,V> e = table[0]; e != null;e = e.next) {// 如果key是nullif (e.key== null) {// 取出oldValue，并存入valueV oldValue = e.value;e.value = value;e.recordAccess(this);// 返回oldValuereturn oldValue;}}modCount++;addEntry(0, null, value, 0);return null;}

         //预处理hash值，避免较差的离散hash序列，导致桶没有充分利用

   static int hash(int h) {

      h ^= (h >>> 20) ^ (h >>> 12);

      return h ^ (h >>> 7) ^ (h >>>4);

    }

           //返回对应hash值得索引 ，h为key的hashCode处理后的值，length为table中Entry数组大小。

 static int indexFor(int h, int length) {/****************** 由于length是2的n次幂，所以h &(length-1)相当于h % length。* 对于length，其2进制表示为1000...0，那么length-1为0111...1。* 那么对于任何小于length的数h，该式结果都是其本身h。* 对于h = length，该式结果等于0。* 对于大于length的数h，则和0111...1位与运算后，* 比0111...1高或者长度相同的位都变成0，* 相当于减去j个length，该式结果是h-j*length，* 所以相当于h % length。* 其中一个很常用的特例就是h & 1相当于h % 2。* 这也是为什么length只能是2的n次幂的原因，为了优化。*/return h & (length-1);
}

8、了解HashMap其他构造函数的源码

       https://github.com/summerxhf/j2ee-demo/blob/master/HashMap-demo/src/main/java/HashMap.java

       我们可以看到，我们在put的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（方法 indexFor），如果数组中的位置上已经有其他元素了，那么这个元素将以链表的形式存放，在链表头中加入新的，最先put的key的value 放在链尾。如果该数组位置上没有元素，则直接将该元素放到改位置上。

9、 一些其他疑问

9.1、对于，put key为null的值呢？

       如果key为null的时候，方法putForNullKey告诉我们答案。

       key为null的时候，value也可以不为null。不过在 addEntry(0, null, value, 0);的时候，存放的hash值，以及数组的下标值为0，key值为null。

       如下图所示，每一行链表中，Entry的key是一个。Entry中有key和value ，以及链表连接指向。

9.2、 有人会问到底啥事hashCode？

       其实就是经过一系列的数学运算，移位运算得到一个数，就成为了hashCode。不解释,看源码哦.

9.3、 Entry的数组的大小，也就是table的大小，为什么必须是2的幂次方？

       HashMap的结构是数组+单链表结构，我们希望元素是均匀分配的，最理想的效果是，Entry中的每个位置都只有应元素，也就是链表的头结点，就是链表的尾节点，这样查询效率最高，不需要遍历链表，有而不需要进行equals比较key，而且利用率最大 ，%取模运算 哈希值%table容量 =数组下标，而代码中这样实现的h & (length-1)，当length总是2的n次方时，h &（length-1）运算等价于对length取模，也就是h%length，但是&比%的效率要高。

9.4、 HashMap线程不安全，那多线程下使用如何做呢？

       1包装一下

       2 Map m =Collections.synchronizedMap(newHashMap(...));

       3使用java.util.HashTable，效率最低

       4使用java.util.concurrent.ConcurrentHashMap，相对安全，效率较高

       接下来一一说明Map接口的其他实现 。

总结

       从如何使用上，key value映射时，HashMap的原理上，一维数组+单链表结构，大概了解了他，总之，追本溯源，很好的了解他，才能很好的控制他。