字典、哈希表、数组的概念

说明：这篇文章也是我从网上查阅资料所学，不代表完全准确性！！仅代表个人想法，欢迎勘误。

重要：不要把抽象的数据结构和底层实现混为一谈。

目录

一、数组

二、字典

三、哈希表

四、总结

---

一、数组

数据结构上称为一维数组，可以用线性表、向量、一维矩阵来存储。

数据结构上称为二维数组，可以用二维矩阵或作为某种其他结构的内部存储。

特点

        1.数组是相同数据类型的元素的集合。

        2.数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。

        3.数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。

二、字典

        字典是一个应用概念，是一个存储键值对的结构，可以用哈希表、红黑树实现。

        所以，很多人都混淆了，字典和哈希表有啥区别，咋那么像呢，都是存储键值对。字典底层就是哈希表（不一定，可能是树）呀！！

三、哈希表

百度百科：“散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

        哈希表中存储着entry，也就是键值对。散列函数对Key进行散列计算得到一个哈希值，这个值就是该键值对在哈希表中的地址。那么可以猜想到，如果哈希函数设计的没那么的好，大概率会产生稀疏，可以理解为一个一维数组，元素随机存储，元素之间间隔N个空位。也就是说，从数学角度上哈希表可能是个稀疏数组。

         如此看来，哈希（散列）函数就极为重要了，一个好的散列算法可以让哈希表接近于数组，而不是稀疏数组（一维矩阵）。

         啥是哈希碰撞呢？就是一个 Entry Key 经过散列后获得一个哈希值，这个值就是它的坑位，然后发现这个坑位已经被占了，这就是哈希碰撞。解决哈希碰撞有两种方法：开链法和开放寻址法。

        开链法很好理解，就是当发现这个坑位被占了，就创建一张链表，哈希表对应位置存储指向这张链表的指针，后来的元素可以按需存放，可以放在链尾，可以插在链头，还可以按大小顺序排放，反正嘛按需选择，链表的增删很是很方便。

       开放寻址法就是当发现这个坑位被占后，接着往下找下一个位置是否被占，如果没有就把这个entry放进去，如果还被占了，就继续往下找，搞定。当然这里介绍的只是一种实现，也有其他的方案，这就是个概念，感兴趣的可以继续Google学习下。

        键值对的数量多了以后，哈希表可能放不下了，那么就要进行扩容啦。有很多不同的扩容方案，其中redis就是有一个扩容因子。比如是0.5，一开始先申请1000个空间，当占用500个位置后，就开始重新申请空间，并且rehash到新的哈希表中，而且redis是渐进式rehash，感兴趣的可以看下这本书，写的很详细，强烈推荐：《redis设计与实现》

        总而言之，哈希表就是一个稀疏数组，当发生哈希碰撞时可以变成稀疏数组+链表或稀疏数组+树。

四、总结

        字典和哈希表都是存储键值对的数据结构，但是字典是应用层的说法，是一种抽象的概念，底层可以是哈希表也可以是红黑树。哈希表的基础数据结构之一是稀疏数组，如果散列函数设计的好，可以类似等于数组，即没有空位。数组则是一种连续存储的数据结构。