4

使用哈希映射时，性能瓶颈通常是equals方法。equals对于深度数据结构来说可能非常昂贵。

请注意，以下是关于不可变哈希映射的。因此，至少您永远不会删除密钥。我认为添加密钥应该没问题。

不安全get

假设您查询一个哈希映射，并确定它包含查询的 key。然后，如果给定键没有冲突，则可以仅基于哈希命中返回找到的单个条目，因为它必须是查询的对象。

这可以避免在大多数情况下调用equals（get当没有碰撞时）。

问题

  1. 这个概念怎么称呼？
  2. 是否有任何可用于 Java 或 Scala 的哈希映射实现支持这种不安全的get操作？

顺便说一句，我愿意接受更好的主题行的建议。

4

4 回答 4

7

这个概念怎么称呼？

身份图。它在查找元素时不会调用equals()，只使用身份（即==）。

正确的解决方案不是“修复”地图，而是仅使用使用默认值的键Object.equals()：

public boolean equals( Object other ) { return this == other; }

问题在于，除非所有键都是单例，否则在此映射中查找元素可能会出现问题。因此，您不能使用String，例如，因为 Java 不能保证所有字符串实例都是实习的。对于以下情况也是如此Integer：实例 < -128 和 > 127 会有所不同。

但是如果你使用自己优化的键实现，你可以解决这个问题。

于 2012-11-19T10:36:03.290 回答
4

据我所知，这种数据结构并不存在，因为它不安全——没有办法可靠地编码您的特定条件。

但是，可惜的是，Scala 集合库允许使用少量新代码非常快速地实现新的丰富数据结构。这是您的请求的实现：

class ParticularHashMap[A, +B] private(buckets: Vector[List[(A, B)]]) extends Map[A, B]{

    def this() = this(Vector.fill(ParticularHashMap.BucketsNo)(List.empty))

    def get(key: A) = {
        val bucket = buckets(bucketIndex(key))

        bucket match {
            case List((_, v)) => Some(v) //YOUR SPECIAL OPTIMIZATION !
            case list => list.find(key == _._1).map(_._2)
        }
    }

    def iterator = buckets.flatten.iterator

    def -(key: A) = mkWithUpdatedBucket(key, _ filterNot (_._1 == key))

    def +[B1 >: B](kv: (A, B1)) = mkWithUpdatedBucket(kv._1, insert(kv._1, kv._2.asInstanceOf[B], _))

    //if you're wondering why it's Bucket[A, Any] and not Bucket[A, B] it's because of the covariance of B
    private def mkWithUpdatedBucket(key: A, f: Bucket[A, Any] => Bucket[A, Any]) = {
        val index = bucketIndex(key)
        val newBucket = f(buckets(index))
        (new ParticularHashMap[A, Any](buckets.updated(index, newBucket))).asInstanceOf[ParticularHashMap[A, B]]
    }

    private def insert(k: A, v: Any, bucket: List[(A, Any)]): Bucket[A, Any] = bucket match {
        case List() => List((k, v))
        case (k1, v1) :: kvs if k == k1 => (k, v) :: kvs
        case (k1, v1) :: kvs => (k1, v1) :: insert(k, v, kvs)
    }

    private def bucketIndex(key: A) = Math.abs(key.hashCode()) % ParticularHashMap.BucketsNo
}

object ParticularHashMap {
    private val BucketsNo = 256

    private type Bucket[+A, +B] = List[(A, B)]

    def apply[A, B](kvs: (A, B)*) = new ParticularHashMap[A, B] ++ kvs

}

请注意，这是一个幼稚的实现，但您可以根据自己的需要对其进行改进。

它将按预期工作：

val myMap = ParticularHashMap("hello" -> 2, "world" -> 4)
println(myMap.get("hello")) >> Some(2)
println(myMap.get("world")) >> Some(4)
println(myMap.get("world1")) >> None

但是，当然要注意，如果你不尊重你的合同，坏事就会发生。下面是一个特别精心设计的例子来展示它的缺点：

val evilMap = ParticularHashMap(1 -> 2)
println(evilMap.get(1)) >> Some(2)
println(evilMap.get(257)) >> Some(2) //BUT 257 IS NOT IN THE MAP !!!
于 2012-11-19T13:40:50.533 回答
0

1）这个概念怎么称呼？

AFAIK，它没有名字。人们通常只为有效的解决方案命名。不起作用的解决方案（或仅在非常有限的情况下有效）通常不值得命名。

2) 是否有任何可用于 Java 或 Scala 的哈希映射实现支持这种不安全的 get 操作？

不是我知道的。再一次，人们倾向于不编写和发布仅在有限情况下工作或行为有问题的库。

它的破绽在哪里？为什么它不起作用？

首先，Map.get(...)如果您给它一个无法识别的键，则返回错误值的方法从根本上破坏了 JavaMap.get契约。很可能还有其他不完善的方法；例如Map.containsKey、Map.put和Map.putAll/或Map.remove。

其次，如果您的假设不正确，则给出错误答案的数据结构是一个坏主意……如果您可以避免的话。

第三，以我们不知道您的实际用例为模，几乎可以肯定有更好的方法来解决问题。显而易见的是：

  • 更改equals密钥类别以降低成本，
  • 如果您不能更改equals、定义和使用代理密钥类，或者
  • 使用 aMap<Integer, List<Pair<Key,ValueClass>>>其中用作键的整数是实际键的哈希码。

（最后一种方法需要可疑的“始终包含密钥”假设，但至少您没有破坏 Map 抽象，因此可以在需要时进行适当的检查。）

最后，即使您确实决定您的“脏”优化对于您的应用程序是必要的，并决定自己实现它。我声称我的回答仍然是正确的解释：

  1. 为什么这个“黑客”没有一个普遍接受的术语，以及
  2. 为什么在 3 个主要的 Java 集合库（或我目前知道的任何其他库）中没有现成的实现。

你可能不喜欢它，但没有更好的解释。

于 2012-11-19T11:38:33.473 回答
0

在这种情况下，您唯一需要的是一个数组，不是吗？

如果您知道没有冲突 - 这意味着没有两个键具有相同的哈希码 - 您可以使用哈希码作为地址来索引数组。例如，如果您的键对象的哈希码之一是 1003，则可以将相应的值对象放入 yourArray[1003]。

如果你买不起巨大的数组，假设你可以执行“不安全”的 get 操作，你可以将地址计算为 key.hashcode() % yourArray.length。每当 key1 和 key2 因为模运算而映射到同一个插槽时，只需覆盖该插槽即可。

class SimpleMap<K, V> {
    private V [] data;

    public SimpleMap(int size){
        data = (V[])new Object[size];
    }

    public void put (K key, V value){
        data[key.hashCode() % data.length] = value;
    }

    public V get(K key) {
        return data[key.hashCode() % data.length];
    }
}
于 2016-10-26T16:39:37.233 回答