当键是唯一的时,Map 可以解决 O(1) 的搜索解。
但是是否存在一种结构,其中按键搜索和值搜索都采用 O(1) 顺序?
给定一个结构:
Put(key,value)
GetValueOf(Key) in O(1)
GetKeyOf(Value) in O(1)
有没有一种方法可以在不使用 2 张地图的情况下按 1 次顺序进行两次搜索?
我对 java 实现特别感兴趣。
提前致谢 !!
当键是唯一的时,Map 可以解决 O(1) 的搜索解。
但是是否存在一种结构,其中按键搜索和值搜索都采用 O(1) 顺序?
给定一个结构:
Put(key,value)
GetValueOf(Key) in O(1)
GetKeyOf(Value) in O(1)
有没有一种方法可以在不使用 2 张地图的情况下按 1 次顺序进行两次搜索?
我对 java 实现特别感兴趣。
提前致谢 !!
您注意到,当键是唯一的时,地图可以解决 O(1) 搜索解决方案。当两个键都是唯一的任何值时,您需要一个 O(1) 搜索解决方案。那么,这个数据结构就足够了:
class YourDoubleHashMap<K,V>() {
private HashMap<K,V> keyMap;
private HashMap<V,K> valMap;
YourDoubleHashMap<K,V>() {
keyMap = new HashMap<K,V>();
valMap = new HashMap<V,K>();
}
public boolean put(K key,V val) {
return keyMap.put(key,val) && valMap.put(val,key);
}
public V getValueOfKey(K key) {
return keyMap.get(key);
}
public K getKeyOfValue(V val) {
return valMap.get(val);
}
}
这种时间-内存权衡方法牺牲了空间效率以换取运行时效率。
在 boost 中有boost::bimap。它基于执行两个映射的两个映射,我相信对于您遇到的问题没有更好的解决方案。
如果您知道如何正确地“散列”值(正确地,我的意思是两个不同的值会很有可能给您两个不同的散列),您可以使用 2 个散列表,(一个从键到值,另一个从值到钥匙)
boost bimap 是一种旨在满足此类要求的数据结构。它非常灵活,查找的复杂性取决于您告诉它用于存储基础值的数据结构。