请你来说一下map和set有什么区别，分别又是怎么实现的？

[问答题]

朗基努斯

map是接口，不提供实现。map的最典型的实现代表是Hashmap, 其底层是数组加链表的形式，数组保存对key哈希后的hash值，称为哈希槽；每个哈希槽后面都挂着一串链表，链表的每个节点都是一个entry,这个entry保存了<key,value>;每次要存某个<key,value>时，先根据key计算其hash值找到对应的槽，再顺着槽后面挂着的entry链表去找有无该key,有则直接更新该key所在entry的value值，无则将该<key,value>包装成entry插入到这个链表的开头；

map是双列集合，同时存储key和value; set是单列集合，只保存一个值。在底层，单列集合是通过屏蔽双列集合的一列来实现保存单列的（Hashset是通过屏蔽HashMap的value列实现的），HashSet把它要存储的值放到HashMap的key中，同时屏蔽掉value;这也解释了为什么HashMap的key不能重复，而HashSet的存的值不能重复，因为本质上两者是一样的。

发表于 2019-06-13 18:19:26 回复(0)