今天在网上看到了一道别人分享的数据结构面试题，要求实现一个key-value容器，支持如下操作：
1.根据key获取元素
2.根据key删除元素
3.插入元素
4.根据value获取key
以上操作时间复杂度均要求在O(log N)以内。
用平衡树可以实现前三条，有没有哪种数据结构可以一并实现第四条的？
收藏
收藏
收藏
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
3
784
一下能想到的是个很二的办法：用两棵树……
没特殊约束的话，说不定我真的会这么实现。
前三个都很好做，但是第四个问题描述得不够清楚，因为可能多个key对应的都是相同的value，所以根据value去获取key就比较麻烦了，结果可能是一个数组。如果保证一一对应，key和value也都是唯一的，那么像楼上说的简单的两棵平衡树就可以解决
java的hashmap源码中是这样实现的，一个数组用来存放key值，根据key的hash值（hash这个值）存储到对应index位置，每个位置从头节点开始，是一个链表，依次把相同key的元素连起来。当遇到相同key的时候就遍历链表进行插入或者查询操作。
这个应该可以满足你的要求吧？