博客

结合项目中用到map的数据结构，在项目中其实用到蛮多的，比如我们数据库表中任何涉及分类的物品存储。可以设置parentId 和 Id，用map查询parentId作为key，用list封装其子类作为value。提前把对应数据从数据库读取到缓存中，提高项目的读写效率和安全性。这就是map在菜单三级分类中的很好的应用。

下面我们来简单介绍一下这个的基础知识吧！

一、Map接口

在生活中我们经常成对的储存某些信息，Map就是用来存储“键(key)-值(value) 对”的。 Map类中存储的“键值对”通过键（key）来标识，所以“key”不能重复。

Map 接口的实现类有HashMap、TreeMap、HashTable、Properties等。

下面是Map接口常用的方法：

二、HashMap

HashMap采用哈希算法实现，是Map接口最常用的实现类。 HashMap在查找、删除、修改方面都有非常高的效率。

HashTable类和HashMap用法几乎一样，底层实现几乎一样，只不过HashTable的方法添加了synchronized关键字确保线程同步检查，效率较低。

1. HashMap: 线程不安全，效率高。允许key或value为null。

2. HashTable: 线程安全，效率低。不允许key或value为null。

HashMap的底层实现：

HashMap底层实现采用了哈希表，这是一种非常重要的数据结构。

数据结构中由数组和链表来实现对数据的存储，他们各有特点。

(1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。

(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。

那么，我们能不能结合数组和链表的优点(即查询快，增删效率也高)呢? 答案就是“哈希表”。 哈希表的本质就是“数组+链表”。

HashMap的底层基本结构

1.HashMap的节点

HashMap是一个集合，键值对的集合,源码中每个节点用Node<K,V>表示

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为值，next指向下一个元素，可以看出HashMap中的元素不是一个单纯的键值对，还包含下一个元素的引用。

2.HashMap的数据结构：数组+(链表或红黑树)

上图：

3.HashMap存储元素的过程：

HashMap<String,String> map = new HashMap<String,String>();
map.put("刘德华","张惠妹");
map.put("张学友","大S");

要把key,value键值对存入map:

第一步,计算出key的hashcode，再对该hashcode取一次hash,该值用来定位要将这个元素存放到数组中的什么位置.

什么是hashcode？

在Object类中有一个方法:

public native int hashCode();

该方法用native修饰，所以是一个本地方法，所谓本地方法就是非java代码，这个代码通常用c或c++写成，在java中可以去调用它。

调用这个方法会生成一个int型的整数，我们叫它哈希码，哈希码和调用它的对象地址和内容有关.

哈希码的特点是:

1）对于同一个对象如果没有被修改（使用equals比较返回true）那么无论何时它的hashcode值都是相同的；

2）对于两个对象如果他们的equals返回false,那么他们的hashcode值也有可能相等。

明白了hashcode我们再来看元素如何通过hashcode定位到要存储在数组的哪里，通过hashcode的二次hash值和数组长度取模我们可以得到元素存储的下标。

比如：key-“刘德华”的hashcode的二次hash值为20977295 数组长度为 16则要存储在数组索引为 20977295%16=1的地方



可以分两种情况:

1. 数组索引为1的地方是空的，这种情况很简单，直接将元素放进去就好了。

2. 已经有元素占据了索引为1的位置，这种情况下我们需要判断一下该位置的元素和当前元素是否相等，使用equals来比较。

如果使用默认的规则是比较两个对象的地址。也就是两者需要是同一个对象才相等，当然我们也可以重写equals方法来实现我们自己的比较规则最常见的是通过比较属性值来判断是否相等。

如果两者相等则直接覆盖，如果不等则在原元素下面使用链表的结构存储该元素。



每个元素节点都有一个next属性指向下一个节点，这里由数组结构变成了数组+链表结构,红黑树又是怎么回事呢？

因为链表中元素太多的时候会影响查找效率，所以当链表的元素个数达到8并且数组长度超过64的时候使用链表存储就转变成了使用红黑树存储，原因就是红黑树是平衡二叉树，在查找性能方面比链表要高。

4.HashMap中的两个重要的参数

HashMap中有两个重要的参数：

初始容量大小

和

加载因子

，初始容量大小是创建时给数组分配的容量大小，默认值为16，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍，专业术语叫做扩容。

在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能。



创建HashMap时我们可以通过合理的设置初始容量大小来达到尽量少的扩容的目的。加载因子也可以设置，但是除非特殊情况不建议设置。