之所以把HashSet和HashMap放在一起讲解，是因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说HashSet里面有一个HashMap（适配器模式）**。因此本文将重点分析HashMap。

HashMap

HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步外，其余跟Hashtable大致相同；跟TreeMap不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。根据对冲突的处理方式不同，哈希表有两种实现方式，一种开放地址方式（Open addressing），另一种是冲突链表方式（Separate chaining with linked lists）。Java HashMap采用的是冲突链表方式。 

从上图容易看出，如果选择合适的哈希函数，put()和get()方法可以在常数时间内完成。但在对HashMap进行迭代时，需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将HashMap的初始大小设的过大。

有两个参数可以影响HashMap的性能：初始容量（inital capacity）和负载系数（load factor）。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。

将对象放入到HashMap或HashSet中时，有两个方法需要特别关心：hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要*@Override*hashCode()和equals()方法。

HashMap

1、为什么用HashMap？

• HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)映射

• HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改

• HashMap是非synchronized，所以HashMap很快

• HashMap可以接受null键和值，而Hashtable则不能（原因就是equlas()方法需要对象，因为HashMap是后出的API经过处理才可以）

2、HashMap的工作原理是什么？

• HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Node 。

方法

方法剖析

get()

get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。算法思想是首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个entry。 

上图中hash(k)&(table.length-1)等价于hash(k)%table.length，原因是HashMap要求table.length必须是2的指数，因此table.length-1就是二进制低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了。

//getEntry()方法final Entry<K,V> getEntry(Object key) {  ......  int hash = (key == null) ? 0 : hash(key);    for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表         e != null; e = e.next) {//依次遍历冲突链表中的每个entry        Object k;        //依据equals()方法判断是否相等        if (e.hash == hash &&            ((k = e.key) == key || (key != null && key.equals(k))))            return e;    }    return null;}


put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，插入方式为头插法。 

//addEntry()void addEntry(int hash, K key, V value, int bucketIndex) {    if ((size >= threshold) && (null != table[bucketIndex])) {        resize(2 * table.length);//自动扩容，并重新哈希        hash = (null != key) ? hash(key) : 0;        bucketIndex = hash & (table.length-1);//hash%table.length    }    //在冲突链表头部插入新的entry    Entry<K,V> e = table[bucketIndex];    table[bucketIndex] = new Entry<>(hash, key, value, e);    size++;}

remove()

remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry（修改链表的相应引用）。查找过程跟getEntry()过程类似。 

//removeEntryForKey()final Entry<K,V> removeEntryForKey(Object key) {  ......  int hash = (key == null) ? 0 : hash(key);    int i = indexFor(hash, table.length);//hash&(table.length-1)    Entry<K,V> prev = table[i];//得到冲突链表    Entry<K,V> e = prev;    while (e != null) {//遍历冲突链表        Entry<K,V> next = e.next;        Object k;        if (e.hash == hash &&            ((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry            modCount++; size--;            if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry            else prev.next = next;            return e;        }        prev = e; e = next;    }    return e;}

HashSet

前面已经说过HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法，因此HashSet的实现非常简单，只有不到300行代码。这里不再赘述。

//HashSet是对HashMap的简单包装public class HashSet<E>{  ......  private transient HashMap<E,Object> map;//HashSet里面有一个HashMap    // Dummy value to associate with an Object in the backing Map    private static final Object PRESENT = new Object();    public HashSet() {        map = new HashMap<>();    }    ......    public boolean add(E e) {//简单的方法转换        return map.put(e, PRESENT)==null;    }    ......}

一、HahMap存储对象的过程如下

1、对HahMap的Key调用hashCode()方法，返回int值，即对应的hashCode；

2、把此hashCode作为哈希表的索引，查找哈希表的相应位置，若当前位置内容为NULL，则把hashMap的Key、Value包装成Entry数组，放入当前位置；

3、若当前位置内容不为空，则继续查找当前索引处存放的链表，利用equals方法，找到Key相同的Entry数组，则用当前Value去替换旧的Value；

4、若未找到与当前Key值相同的对象，则把当前位置的链表后移（Entry数组持有一个指向下一个元素的引用），把新的Entry数组放到链表表头；

二、HashSet存储对象的过程

往HashSet添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值 ，

然后通过元素 的哈希值经过移位等运算，就可以算出该元素在哈希表中 的存储位置。

情况1：如果算出元素存储的位置目前没有任何元素存储，那么该元素可以直接存储到该位置上。

情况2：如果算出该元素的存储位置目前已经存在有其他的元素了，那么会调用该元素的equals方法与该位置的元素再比较一次

，如果equals返回的是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素运行添加。

             

题外话：

这Typora还夸你好用还免费，这突然更新了就啪啪打脸了，那问题来了typora是啥？

Typora，异常纯净的写作软件。支持 Markdown 语法、一键导出为各种文档格式、图床一键上传等核心功能，可以满足几乎所有同学的写作、记录需求。

因为界面干净清爽、细节到位、写作体验巨好，这款软件被很多同学称为是 “艺术品” 。我自己作为 Typora 的忠实用户，用了它之后再也没用过别的本地写作软件（比如开源的 Mark Text）。我甚至可以为了它的写作体验，而放弃一些云端自动同步的产品（现在我都是用 Git + GitHub 私仓来管理所有的文档了）。

再加上它是完全免费的，使得这个软件得到了无数小伙伴的好评。

但是，就在前两天，Typora 的作者 Abner Lee 突然宣布：升级 v1.x 正式版本后，Typora 将 收费 ！折合人民币 90 元左右，可以在最多 3 台设备使用。不过 v1.0 前的老版本依然可以免费使用。

估计有很多同学要问了：小刘，Typora 收费了，值得买么？

我说下自己的看法：可以付费，但没必要。

首先，我也是一名开发者，当然理解开发免费软件的艰辛，也对作者这么多年来持续更新免费产品表示 100% 的敬佩。

但是，暂且不摆对这个软件的情怀，单纯从用户的角度来看，付费版本并没有比免费版本多出什么功能和亮点。看一下官方的 CHANGE LOG，发现只是多了个安装包、一些数学公式编辑和 Bug 修复而已。

所以我是不会购买的。而且作者已经那么良心了 —— 老的 beta 版本还能直接在官网下载、免费使用，我们当然不能辜负作者的一片好意（狗头）。

我希望收费之后的 Typora 可以在不影响用户使用习惯的前提下，打磨地更好、出一些更实用的功能（比如云端同步、插件等），等到那时，我可能不仅会付费购买，还会做一波无偿推广哈哈~

总结：

1. java最基本的两种数据结构：数组和链表的区别：数组易于快速读取（通过for循环），不便存储（数组长度有限制）；链表易于存储，不易于快速读取。

2. HashSet是通过HasMap来实现的，HashMap的输入参数有Key、Value两个组成，在实现HashSet的时候，保持HashMap的Value为常量，相当于在HashMap中只对Key对象进行处理。

3. HashMap的底层是一个数组结构，数组中的每一项对应了一个链表，这种结构称“链表散列”的数据结构，即数组和链表的结合体；也叫散列表、哈希表。

4. jdk1.8以前的hashmap与jdk1.8以后的hashmap

5. 你要知道两种方式的存储和底层逻辑和方法的使用

6. 这Typora 的作者还是很良心的v1.x以前的还是免费，而且以前的版本可以在官网下载，这工具来写文章或者做笔记还是很棒的。