You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hive.apache.org by tc...@apache.org on 2018/11/27 11:09:05 UTC
hive git commit: HIVE-20873: Use Murmur hash for
VectorHashKeyWrapperTwoLong to reduce hash collision (Teddy Choi,
reviewed by Gopal V)
Repository: hive
Updated Branches:
refs/heads/master 7c5b99b5b -> dffa3a165
HIVE-20873: Use Murmur hash for VectorHashKeyWrapperTwoLong to reduce hash collision (Teddy Choi, reviewed by Gopal V)
Project: http://git-wip-us.apache.org/repos/asf/hive/repo
Commit: http://git-wip-us.apache.org/repos/asf/hive/commit/dffa3a16
Tree: http://git-wip-us.apache.org/repos/asf/hive/tree/dffa3a16
Diff: http://git-wip-us.apache.org/repos/asf/hive/diff/dffa3a16
Branch: refs/heads/master
Commit: dffa3a16588bc8e95b9d0ab5af295a74e06ef702
Parents: 7c5b99b
Author: Teddy Choi <pu...@gmail.com>
Authored: Tue Nov 27 20:08:04 2018 +0900
Committer: Teddy Choi <pu...@gmail.com>
Committed: Tue Nov 27 20:08:04 2018 +0900
----------------------------------------------------------------------
.../apache/hive/common/util/HashCodeUtil.java | 13 ++---
.../wrapper/VectorHashKeyWrapperTwoLong.java | 4 +-
.../org/apache/hive/common/util/Murmur3.java | 57 +++++++++++++++++---
.../apache/hive/common/util/TestMurmur3.java | 47 ++++++++++++++++
4 files changed, 103 insertions(+), 18 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
----------------------------------------------------------------------
diff --git a/common/src/java/org/apache/hive/common/util/HashCodeUtil.java b/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
index 700b2e1..1330cbe 100644
--- a/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
+++ b/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
@@ -33,15 +33,12 @@ public class HashCodeUtil {
return key;
}
+ public static int calculateTwoLongHashCode(long l0, long l1) {
+ return Murmur3.hash32(l0, l1);
+ }
+
public static int calculateLongHashCode(long key) {
- // Mixing down into the lower bits - this produces a worse hashcode in purely
- // numeric terms, but leaving entropy in the higher bits is not useful for a
- // 2^n bucketing scheme. See JSR166 ConcurrentHashMap r1.89 (released under Public Domain)
- // Note: ConcurrentHashMap has since reverted this to retain entropy bits higher
- // up, to support the 2-level hashing for segment which operates at a higher bitmask
- key ^= (key >>> 7) ^ (key >>> 4);
- key ^= (key >>> 20) ^ (key >>> 12);
- return (int) key;
+ return Murmur3.hash32(key);
}
public static void calculateLongArrayHashCodes(long[] longs, int[] hashCodes, final int count) {
http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
----------------------------------------------------------------------
diff --git a/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java b/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
index 1652728..c40c35d 100644
--- a/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
+++ b/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
@@ -44,9 +44,7 @@ public class VectorHashKeyWrapperTwoLong extends VectorHashKeyWrapperTwoBase {
HashCodeUtil.calculateLongHashCode(longValue0) ^
null1Hashcode));
} else {
- hashcode =
- HashCodeUtil.calculateLongHashCode(longValue0) >>> 16 ^
- HashCodeUtil.calculateLongHashCode(longValue1);
+ hashcode = HashCodeUtil.calculateTwoLongHashCode(longValue0, longValue1);
}
}
http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
----------------------------------------------------------------------
diff --git a/storage-api/src/java/org/apache/hive/common/util/Murmur3.java b/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
index 8aae28b..85db95c 100644
--- a/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
+++ b/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
@@ -54,6 +54,43 @@ public class Murmur3 {
public static final int DEFAULT_SEED = 104729;
+ public static int hash32(long l0, long l1) {
+ return hash32(l0, l1, DEFAULT_SEED);
+ }
+
+ public static int hash32(long l0) {
+ return hash32(l0, DEFAULT_SEED);
+ }
+
+ /**
+ * Murmur3 32-bit variant.
+ */
+ public static int hash32(long l0, int seed) {
+ int hash = seed;
+ final long r0 = Long.reverseBytes(l0);
+
+ hash = mix32((int) r0, hash);
+ hash = mix32((int) (r0 >>> 32), hash);
+
+ return fmix32(Long.BYTES, hash);
+ }
+
+ /**
+ * Murmur3 32-bit variant.
+ */
+ public static int hash32(long l0, long l1, int seed) {
+ int hash = seed;
+ final long r0 = Long.reverseBytes(l0);
+ final long r1 = Long.reverseBytes(l1);
+
+ hash = mix32((int) r0, hash);
+ hash = mix32((int) (r0 >>> 32), hash);
+ hash = mix32((int) (r1), hash);
+ hash = mix32((int) (r1 >>> 32), hash);
+
+ return fmix32(Long.BYTES * 2, hash);
+ }
+
/**
* Murmur3 32-bit variant.
*
@@ -108,12 +145,7 @@ public class Murmur3 {
| ((data[offset + i_4 + 2] & 0xff) << 16)
| ((data[offset + i_4 + 3] & 0xff) << 24);
- // mix functions
- k *= C1_32;
- k = Integer.rotateLeft(k, R1_32);
- k *= C2_32;
- hash ^= k;
- hash = Integer.rotateLeft(hash, R2_32) * M_32 + N_32;
+ hash = mix32(k, hash);
}
// tail
@@ -134,7 +166,18 @@ public class Murmur3 {
hash ^= k1;
}
- // finalization
+ return fmix32(length, hash);
+ }
+
+ private static int mix32(int k, int hash) {
+ k *= C1_32;
+ k = Integer.rotateLeft(k, R1_32);
+ k *= C2_32;
+ hash ^= k;
+ return Integer.rotateLeft(hash, R2_32) * M_32 + N_32;
+ }
+
+ private static int fmix32(int length, int hash) {
hash ^= length;
hash ^= (hash >>> 16);
hash *= 0x85ebca6b;
http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
----------------------------------------------------------------------
diff --git a/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java b/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
index 16955c1..7320d6d 100644
--- a/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
+++ b/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
@@ -270,4 +270,51 @@ public class TestMurmur3 {
assertEquals("Block size " + blockSize, expected, diff.end());
}
}
+
+ @Test
+ public void testTwoLongOrdered() {
+ ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES * 2);
+ for (long i = 0; i < 1000; i++) {
+ for (long j = 0; j < 1000; j++) {
+ buffer.putLong(0, i);
+ buffer.putLong(Long.BYTES, j);
+ assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(i, j));
+ }
+ }
+ }
+
+ @Test
+ public void testTwoLongRandom() {
+ ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES * 2);
+ Random random = new Random();
+ for (long i = 0; i < 1000; i++) {
+ for (long j = 0; j < 1000; j++) {
+ long x = random.nextLong();
+ long y = random.nextLong();
+ buffer.putLong(0, x);
+ buffer.putLong(Long.BYTES, y);
+ assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(x, y));
+ }
+ }
+ }
+
+ @Test
+ public void testSingleLongOrdered() {
+ ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES);
+ for (long i = 0; i < 1000; i++) {
+ buffer.putLong(0, i);
+ assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(i));
+ }
+ }
+
+ @Test
+ public void testSingleLongRandom() {
+ ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES);
+ Random random = new Random();
+ for (long i = 0; i < 1000; i++) {
+ long x = random.nextLong();
+ buffer.putLong(0, x);
+ assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(x));
+ }
+ }
}