字典这种数据结构在现代的开发语言中比较常见(PHP叫关联数组)

探索一下其底层原理。

概述

现在市面上有很多的场景需要Key-Value对存储方式。比如iOS的键值编码,后端的缓存(Redis和Memcached),和一些KVStore配置等都需要这种结构存储。为什么不用数组,链表等其他方式呢?因为它“快”,为什么快呢?下面就来探索一下。

哈希表(散列表)

根据关键字(Key Value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称作散列函数,存放记录的数组成为散列表。

哈希函数(散列函数)

哈希冲突

当两个Key值通过哈希函数映射的索引为同一位置时,则产生哈希冲突

解决方法:

负载因子

填入表中的元素个数 / 哈希表的长度