【C++面试知识】map的底层实现及其相关
map的底层是红黑树实现的；而在查阅资料过程中出现多次的HashMap，其实是java里的一个容器，java面试时经常问的一个问题就是HashMap的实现方式，是有哈希表（hash table）实现的。另外C++中其实也有类似的容器叫unordered_map，它也是由哈希表实现的。红黑树VS哈希表红黑树存储结构的存取是O(logn)，而哈希表是O(1),当然这是在哈希表没有冲突的...
·
map的底层是红黑树实现的；
而在查阅资料过程中出现多次的HashMap，其实是java里的一个容器，java面试时经常问的一个问题就是HashMap的实现方式，是有哈希表（hash table）实现的。
另外C++中其实也有类似的容器叫unordered_map，它也是由哈希表实现的。
红黑树VS哈希表
红黑树存储结构的存取是O(logn)，而哈希表是O(1),当然这是在哈希表没有冲突的情况下的，但实际的hashmap和unordered_map是不允许冲突的。而红黑树的内存占用要比哈希表高。
红黑树存储是有序的，也就是说map容器里面的元素是按关键字排好序的（<），而unordered_map是无序的。
哈希表很简单，但红黑树是个啥？
写这篇文章的时候我也不是很清楚，慢慢来嘛。
下篇文章我搞一下红黑树吧。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)