java CRC16算法，分解一个大Key实例。和各种hash算法代码

xiaoxiao2021-03-25 115

[java] view plain copy package org.rui.hi; /** * 测试：解决场景:把1亿的用户存储在一个队列里，过大。用sharding 摸拟redis 集群 sharding Redis * 集群使用数据分片（sharding）而非一致性哈希（consistency hashing）来实现：一个 Redis 集群包含 16384 * 个哈希槽（hash slot），数据库中的每个键都属于这 16384 个哈希槽的其中一个，集群使用公式 CRC16(key) % 16384 来计算键 * key 属于哪个槽，其中 CRC16(key) 语句用于计算键 key 的 CRC16 校验和。 * * @author ruiliang * */ public class HashDist { public final static int maxInt = 1000;// 00000;//1亿 public final static int USER_KEY_SLOT_COUNT = 20; // 定议分配存储用户的Slot位 // ，如果存储有压力，可调大槽位 public static void main(String[] args) { // int 不用crc16 for (int i = 1; i < maxInt; i++) { // 根据玩家id 分布指定到Slot位 int ranint = i % USER_KEY_SLOT_COUNT; String key = "key:" + ranint; System.out.println("key:" + key); // redisList.lpush(randomKey, String.valueOf(playerId)); } /** * crc16 redis 集群也是用这种方式分配key */ String a = "a,b,c,d,e,f,g,g,g"; for (String j : a.split(",")) { int solt = CRCJava.crc16(j.getBytes()) % USER_KEY_SLOT_COUNT; String key = "key:" + solt; System.out.println("crc%solt=key:" + key); } // redisList.lpush(randomKey, String.valueOf(playerId)); } } /** * output: ... * * key:key:0 key:key:1 key:key:2 key:key:3 key:key:4 key:key:5 key:key:6 * key:key:7 key:key:8 key:key:9 key:key:10 key:key:11 key:key:12 key:key:13 * key:key:14 key:key:15 key:key:16 key:key:17 key:key:18 key:key:19 key:key:0 * key:key:1 key:key:2 key:key:3 key:key:4 key:key:5 key:key:6 key:key:7 * key:key:8 key:key:9 key:key:10 key:key:11 key:key:12 key:key:13 key:key:14 * key:key:15 key:key:16 key:key:17 key:key:18 key:key:19 key:key:0 key:key:1 * key:key:2 key:key:3 key:key:4 key:key:5 key:key:6 key:key:7 key:key:8 * key:key:9 key:key:10 key:key:11 key:key:12 key:key:13 key:key:14 key:key:15 * key:key:16 key:key:17 key:key:18 key:key:19 key:key:0 key:key:1 key:key:2 * key:key:3 key:key:4 key:key:5 key:key:6 key:key:7 key:key:8 key:key:9 * key:key:10 key:key:11 key:key:12 key:key:13 key:key:14 key:key:15 key:key:16 * key:key:17 key:key:18 key:key:19 key:key:0 key:key:1 key:key:2 key:key:3 * key:key:4 key:key:5 key:key:6 key:key:7 key:key:8 key:key:9 key:key:10 * key:key:11 key:key:12 key:key:13 key:key:14 key:key:15 key:key:16 key:key:17 * key:key:18 key:key:19 key:key:0 key:key:1 key:key:2 key:key:3 key:key:4 * key:key:5 key:key:6 key:key:7 key:key:8 key:key:9 key:key:10 key:key:11 * key:key:12 key:key:13 key:key:14 key:key:15 key:key:16 key:key:17 key:key:18 * key:key:19 crc%solt=key:key:11 crc%solt=key:key:8 crc%solt=key:key:17 * crc%solt=key:key:10 crc%solt=key:key:19 crc%solt=key:key:16 * crc%solt=key:key:5 crc%solt=key:key:5 crc%solt=key:key:5 */

[java] view plain copy package org.rui.hi; public class CRCJava { public static void main(String[] args) { String a = "a,b,c,d,e,f,g"; for (String i : a.split(",")) { System.out.println(crc16(i.getBytes())); } System.out.println("----------------------------------"); for (String i : a.split(",")) { System.out.println(crc162(i.getBytes())); } } /****************************************************************************** * Compilation: javac CRC16CCITT.java Execution: java CRC16CCITT s * Dependencies: * * Reads in a sequence of bytes and prints out its 16 bit Cylcic Redundancy * Check (CRC-CCIIT 0xFFFF). * * 1 + x + x^5 + x^12 + x^16 is irreducible polynomial. * * % java CRC16-CCITT 123456789 CRC16-CCITT = 29b1 * ******************************************************************************/ public static int crc16(final byte[] buffer) { int crc = 0xFFFF; // initial value 65535 int polynomial = 0x1021; // 0001 0000 0010 0001 (0, 5, 12) // byte[] testBytes = "123456789".getBytes("ASCII"); for (byte b : buffer) { for (int i = 0; i < 8; i++) { boolean bit = ((b >> (7 - i) & 1) == 1); boolean c15 = ((crc >> 15 & 1) == 1); crc <<= 1; if (c15 ^ bit) crc ^= polynomial; } } return crc &= 0xffff; } /** * * @param buffer * @return */ static int crc162(final byte[] buffer) { int crc = 0xFFFF; for (int j = 0; j < buffer.length; j++) { crc = ((crc >>> 8) | (crc << 8)) & 0xffff; crc ^= (buffer[j] & 0xff);// byte to int, trunc sign crc ^= ((crc & 0xff) >> 4); crc ^= (crc << 12) & 0xffff; crc ^= ((crc & 0xFF) << 5) & 0xffff; } crc &= 0xffff; return crc; } } ---------------------------------------

各种hash算法

[java] view plain copy package org.rui.hi; /** * 相关hash算法 * * @author ruiliang * */ public class HashTest { public static void main(String[] args) { // long hash = DEKHash("123456"); // System.out.println(hash); System.out.println(hashCode(0)); System.out.println(hashCode(1)); System.out.println(hashCode(2)); System.out.println(hashCode(3)); System.out.println(hashCode(123456)); System.out.println(hashCode(123457)); System.out.println(hashCode(123458)); System.out.println(PJWHash("0")); System.out.println(PJWHash("1")); System.out.println(PJWHash("2")); System.out.println(PJWHash("3")); System.out.println(PJWHash("123456")); System.out.println(PJWHash("123457")); System.out.println(PJWHash("123458")); } /** * 从Robert Sedgwicks的 Algorithms in C一书中得到了 * * @param str * @return */ public static long RSHash(String str) { int b = 378551; int a = 63689; long hash = 0; for (int i = 0; i < str.length(); i++) { hash = hash * a + str.charAt(i); a = a * b; } return hash; } /** * Justin Sobel写的一个位操作的哈希函数。 * * @param str * @return */ public static long JSHash(String str) { long hash = 1315423911; for (int i = 0; i < str.length(); i++) { hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2)); } return hash; } /** * PJW 该散列算法是基于贝尔实验室的彼得J温伯格的的研究。在Compilers一书中（原则，技术和工具），建议采用这个算法的散列函数的哈希方法。 * * @param str * @return */ public static long PJWHash(String str) { long BitsInUnsignedInt = (long) (4 * 8); long ThreeQuarters = (long) ((BitsInUnsignedInt * 3) / 4); long OneEighth = (long) (BitsInUnsignedInt / 8); long HighBits = (long) (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); long hash = 0; long test = 0; for (int i = 0; i < str.length(); i++) { hash = (hash << OneEighth) + str.charAt(i); if ((test = hash & HighBits) != 0) { hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits)); } } return hash; } /** * ELF 和PJW很相似，在Unix系统中使用的较多。 * * @param str * @return */ public static long ELFHash(String str) { long hash = 0; long x = 0; for (int i = 0; i < str.length(); i++) { hash = (hash << 4) + str.charAt(i); if ((x = hash & 0xF0000000L) != 0) { hash ^= (x >> 24); } hash &= ~x; } return hash; } /** * BKDR 这个算法来自Brian Kernighan 和 Dennis Ritchie的 The C Programming * Language。这是一个很简单的哈希算法,使用了一系列奇怪的数字,形式如31,3131,31...31,看上去和DJB算法很相似。 * * @param str * @return */ public static long BKDRHash(String str) { long seed = 131; // 31 131 1313 13131 131313 etc.. long hash = 0; for (int i = 0; i < str.length(); i++) { hash = (hash * seed) + str.charAt(i); } return hash; } public static long SDBMHash(String str) { long hash = 0; for (int i = 0; i < str.length(); i++) { hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash; } return hash; } /** * DJB 这个算法是Daniel J.Bernstein 教授发明的，是目前公布的最有效的哈希函数。 * * @param str * @return */ public static long DJBHash(String str) { long hash = 5381; for (int i = 0; i < str.length(); i++) { hash = ((hash << 5) + hash) + str.charAt(i); } return hash; } /** * .DEK 由伟大的Knuth在《编程的艺术第三卷》的第六章排序和搜索中给出。 * * @param str * @return */ public static long DEKHash(String str) { long hash = str.length(); for (int i = 0; i < str.length(); i++) { hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i); } return hash; } /** * jdk hash * * @param a * @return */ public static int hashCode(int a) { final int prime = 48; int result = 1; result = prime * result + a; return result; } }

转载请注明原文地址: https://ju.6miu.com/read-10120.html

技术

最新回复(0)