如何使用两个数字作为Map键
我有两个数字,我想将它们一起用作Map
的键。 目前,我正在连接他们的字符串表示。 例如,假设密钥号是4和12.我使用:
String key = 4 + "," + 12;
地图声明为Map
。
我觉得这太糟糕了! 我喜欢使用String
以外的东西作为关键! 我想要以最快的方式创建这些密钥。
谁有个好主意?
创建一个包含两个数字的对象并将其用作键。 例如:
class Coordinates { private int x; private int y; public Coordinates(int x, int y) { ... } // getters // equals and hashcode using x and y } Map locations = new HashMap();
如果您更喜欢数学方法,请参阅此StackOverflow答案 。
您应该使用java.awt.Dimension作为密钥。
尺寸键=新尺寸(4,12);
Dimension有一个非常好的hashCode()方法,它为每对正整数产生不同的hashCode,因此(4,12)和(12,4)的hashCodes是不同的。 因此,这些可以快速实例化并生成非常好的hashCodes。
我希望他们让类不可变,但你可以在Dimension上建立自己的不可变类。
这是一个表格,显示了不同宽度和高度值的hashCode:
0 1 2 3 4 <-- width +-------------------- 0 | 0 2 5 9 14 1 | 1 4 8 13 2 | 3 7 12 3 | 6 11 4 | 10 ^ | height
如果按照0到14的顺序执行hashCodes,您将看到该模式。
这是生成此hashCode的代码:
public int hashCode() { int sum = width + height; return sum * (sum + 1)/2 + width; }
您可能会在最后一行中识别出三角形数字的公式。 这就是为什么表格的第一列包含所有三角形数字的原因。
对于速度,您应该在构造函数中计算hashCode。 所以你的全class可能看起来像这样:
public class PairHash { private final int hash; public PairHash(int a, int b) { int sum = a+b; hash = sum * (sum+1)/2 + a; } public int hashCode() { return hash; } }
当然,如果你可能需要一个equals方法,但是你将自己限制为不会溢出的正整数,你可以添加一个非常快的方法:
public class PairHash { // PAIR_LIMIT is 23170 // Keeping the inputs below this level prevents overflow, and guarantees // the hash will be unique for each pair of positive integers. This // lets you use the hashCode in the equals method. public static final int PAIR_LIMIT = (int) (Math.sqrt(Integer.MAX_VALUE))/2; private final int hash; public PairHash(int a, int b) { assert a >= 0; assert b >= 0; assert a < PAIR_LIMIT; assert b < PAIR_LIMIT; int sum = a + b; hash = sum * (sum + 1) / 2 + a; } public int hashCode() { return hash; } public boolean equals(Object other) { if (other instanceof PairHash){ return hash == ((PairHash) other).hash; } return false; } }
我们将此限制为正值,因为负值将产生一些重复的哈希码。 但是有了这个限制,这些是可以编写的最快的hashCode()和equals()方法。 (当然,通过计算构造函数中的hashCode,您可以在任何不可变类中快速编写hashCodes。)
如果你不能忍受这些限制,你只需要保存参数。
public class PairHash { private final int a, b, hash; public PairHash(int a, int b) { this.a = a; this.b = b; int sum = a+b; hash = sum * (sum+1)/2 + a; } public int hashCode() { return hash; } public boolean equals(Object other) { if (other instanceof PairHash) { PairHash otherPair = (PairHash)other; return a == otherPair.a && b == otherPair.b; } return false; }
但这是踢球者。 你根本不需要这个课程。 由于公式为每对数字提供了一个唯一的整数,因此您可以将该整数用作地图关键字。 Integer类有自己的快速equals()和hashCode方法,可以正常工作。 此方法将从两个短值生成散列键。 限制是您的输入需要是正值短值。 这保证不会溢出,并且通过将中间和转换为long,它具有比前一方法更宽的范围:它适用于所有正的短值。
static int hashKeyFromPair(short a, short b) { assert a >= 0; assert b >= 0; long sum = (long) a + (long) b; return (int) (sum * (sum + 1) / 2) + a; }
如果您使用对象解决方案,请确保您的密钥对象是不可变的 。
否则,如果某人改变了值,它不仅不再等于其他明显相同的值,而且存储在地图中的哈希码将不再与hashCode()
方法返回的哈希码相匹配。 那时你基本上是SOL。
例如,使用java.awt.Point
– 在纸上看起来就像你想要的那样 – 以下内容:
public static void main(String[] args) { Map map = new HashMap(); Point key = new Point(1, 3); Object val = new Object(); map.put(key, val); System.out.println(map.containsKey(key)); System.out.println(map.containsKey(new Point(1, 3))); // equivalent to setLeft() / setRight() in ZZCoder's solution, // or setX() / setY() in SingleShot's key.setLocation(2, 4); System.out.println(map.containsKey(key)); System.out.println(map.containsKey(new Point(2, 4))); System.out.println(map.containsKey(new Point(1, 3))); }
打印:
true true false false false
你可以像这样存储两个整数,
long n = (l << 32) | (r & 0XFFFFFFFFL);
或者您可以使用以下Pair
类,
public class Pair { private L l; private R r; public Pair() { } public Pair(L l, R r) { this.l = l; this.r = r; } public L getLeft() { return l; } public R getRight() { return r; } @Override public boolean equals(Object o) { if (!(o instanceof Pair)) { return false; } Pair obj = (Pair) o; return l.equals(obj.l) && r.equals(obj.r); } @Override public int hashCode() { return l.hashCode() ^ r.hashCode(); } }
这个问题的实际答案是:
hashCode = a + b * 17;
…其中a,b和hashCode都是整数。 17只是一个任意的素数。 你的哈希值不是唯一的,但没关系。 这种东西在整个Java标准库中使用。
另一种方法是使用嵌套映射:
Map>
这里没有创建密钥的开销。 但是,您需要更多的开销才能正确创建和检索条目,并且您总是需要映射访问才能找到您要查找的对象。
为什么要编写所有额外的代码来创建一个你不需要其他任何东西的完整类,比使用简单的String更好? 计算该类实例的哈希码会比String更快吗? 我不这么认为。
除非您在极其有限的计算能力环境中运行,否则制作和散列字符串的开销不应明显大于实例化自定义类的开销。
我想最快的方法就是像ZZ Coder建议的那样简单地将整数打包成一个Long,但无论如何,我不认为速度增长是巨大的。
您需要编写正确的eqauls和hashcode方法,否则会产生一些错误。
- Spring / Java中的调度任务
- 带有“DerInputStream.getLength()的Java APNS证书错误:lengthTag = 109,太大了。”
- (JAVA)使用命令提示符从多个.class文件创建.jar文件
- 限制App Engine对自定义域上的G Suite帐户的访问权限
- 通过java中的reflection设置对象字段的值
- 具有不同初始容量和负载因子的HashMap的性能
- 在Java中更改参数是一个好习惯
- Runtime.getRuntime()。exec(“C:\ cygwin \ bin \ bash.exe”)没有输入读取
- 将单个runnable对象传递给多个线程构造函数