1  哈希Map

今天要聊的，是一个在Java/Android面试中被问烂了的类: Hashmap.

这个类如此的被看重，上至阿里 高P面试，下到 数据结构入门教材。  

甚至刚上门取件的快递小哥都能跟你用背课文的语气侃侃而谈，hashmap的底层是数组加链表。

但是今天要聊的又有点不太一样。你真的知道啥是hashmap，为啥要数组加链表吗？

2    散列表

一切都要从数据结构说起 .   曾经有一位大佬说过  程序= 数据结构+算法。

数据结构分为两类：

1  是数据的逻辑结构：  也就是数据元素之间的逻辑关系

数据的逻辑结构

2   是数据的储存结构   是指数据结构在计算机中的表示，又称物理结构。

数据的储存结构是逻辑结构使用计算机语言的实现。

分为四类：  顺序，链表，索引和散列。 

这四类数据结构又被广大码农亲切的称为 "茴"字的四种写法。

咱们今天要聊的HashMap 在逻辑逻辑上属于广义表，在储存结构上散列。

合起来可以称其为 散列表。

3    散列表的特点和用途

讲了这么多理论，那么Hashmap 有什么特点，什么时候使用它啊。

hashmap的时间复杂度 为O(1)（理想情况），空间复杂度 为  N / 扩容因子

通俗一点来说， hashmap 是一个查询速度快（常数级别），内存占用多（内存使用有效率低于扩容因子）的数据结构。

良心的说，Hashmap 和他的近亲 treemap 相比，其实并不适合在内存紧张的移动端使用。

正是因为如此，google 也推出了ArrayMap,sparseArray 来替代hashmap。

以下是性能对比图

插入，查询五万条数据

但是对于一些要求响应速度的场景，比如 api响应,或者 算密集型场景，以及很多sdk项目中，hashmap还是很常见的。

那么接下来我们使用C语言 来手动实现一个散列表。

使用C来实现有两个原因：

1      C语言更贴近硬件，手动分配内存的过程，能更好的表示散列表的数据构建过程

2       前段时间做的项目，正好需要一个 运行在android NDK 上的缓存组件。

4   什么是特么的散列表

下面列出的是 hashmap.h 的内容。

类似于Java中的接口。 实现了下列功能，对外，我们就认为他是一个可使用的散列表。

结构体部分定义 增删，重建函数 内部使用的函数声明

5   哈希和散列

我们要明白 哈希和散列 其实就是一回事儿。   

通俗讲就是讲各种各样，千奇百怪的东西，通过一个算法，成为特定的有规律的东西。这个算法就叫做hash/散列算法。

比如你现在要手里攥了一把葱花，要把他分散的放到一张大饼上去。 这个撒葱花的过程就叫散列。

葱花饼

散列算法有各种各样的实现。  能够让把葱花撒的又快，又均匀的方法就是较优的hash算法。

查看jdk源码，我们会发现， 

object的hash算法是取内存地址的偏移量

obj的hash实现

string的hash算法是 所有的字符单个*31再相加。

String

int的hash算法是其数值本身。

Integer

那我们的hash算法呢？

我们的散列算法实现

我们的hash算法分为两部

第一步是 类似Java的String，将所有字符*31相加。得到一个唯一值。

第二步，根据当前的容量大小，取余。

我得承认这个算法看上去很蠢、

但这是我经过试验之后能想到最好的散列算法了。如果有更好的想法，欢迎留言我。

6  hash冲撞

当我们对这张散列表进行  增删查操作时，

第一步就是上面提到了撒葱花操作，先计算出这个葱花应该在的位置。然后在对这个葱花进行处理。

但是问题在于 再优秀的散列算法也没办法保证  不会有两个葱花放到同样的一个位置。

那么一个合格的hashmap组件一定要处理hash碰撞的情况。先来看看Java8是怎么做的

java8/android实现

（为什么采用红黑树，而不是其他树结构，也是值得拉出来聊聊的。但这不是我们要聊的重点，下次再说。）

我们的hash冲突处理情况稍微简单一些。如果冲突就以链表进行处理。这其实也是Java7之前的处理方式。

我们的add函数

与此对应的，删除也是同样的道理，通过hash算法找到位置之后。如果存在的是一个链表，则对其进行遍历查询操作。

移除函数

7    使用示例

8   性能测试

12000条数据随机查询对比

treemap和hashmap对比

接下来加上 我们手写的hashmap组件 对比一下查询速度

我们手写的map

嗯，这个故事告诉我们一个道理。  牛不牛逼和语言关系不大。 C语言用的不好，还不如Java呢。

完