public final class Demo {
private static int cap;
private static int size = 0;
private static Node[] map;
private static final int LINK = 0;
public Demo(int cap) {
cap = _tableSizeFor(cap);
Demo.cap = cap;
map = new Node[cap];
}
public void put(byte[] key, long val) {
_put(key, val, cap, map);
}
private static void _put(byte[] key, long val, int cap, Node[] map) {
long hash = _hash(key);
int index = _getIndex(hash, cap);
Node head;
if ((head = map[index]) == null) {
map[index] = new Node(key, val, hash);
} else {
if (head.type == LINK) {
int size = 1;
Node p;
do {
++size;
if (head.hash == hash && Arrays.equals(key, head.key)) {
head.val = val;
return;
}
p = head;
head = head.next;
} while (head != null);
p.next = new Node(key, val, hash);
if (size == 8) {
System.out.println("转树了");
}
} else {
System.out.println("树插入");
}
if (++Demo.size == cap) _expansion();
}
}
private static void _expansion() {
Node[] newMap = new Node[cap << 1];
for (int i = 0; i < cap; ++i) {
Node c = map[i];
if (c != null) {
Node next;
do {
next = c.next;
c.next = null;
_put(c.key, c.val, cap << 1, newMap);
c = next;
} while (c != null);
}
}
cap <<= 1;
map = newMap;
}
private static int _tableSizeFor(int cap) {
--cap;
cap |= cap >>> 1;
cap |= cap >>> 2;
cap |= cap >>> 4;
cap |= cap >>> 8;
cap |= cap >>> 16;
return (cap < 0) ? 1 : cap + 1;
}
// 3 4198 1000W 47.29578495025635
// 5 4198 1000W 47.44309186935425
// 20 4198 1000W 47.55440950393677
// 10 4198 1000W 47.58404493331909
// 26 4198 1000W 47.679245471954346
// 19 4198 1000W 47.803592681884766
// 15 4198 1000W 47.8635311126709
// 1 4198 1000W 47.87636995315552
// 21 4198 1000W 47.886037826538086
// 14 4198 1000W 47.95495271682739
// 378551 435 1000W 48.08
// 0x100000001b3L 0x100000001b3L 1000W 48.30
// 1 83535 1000W 48.35
// 0 23781 300W 44
// 485103
private static long _hash(byte[] bytes) {
long result = 3;
for (byte b : bytes)
result = 4198 * result + b;
return result;
}
private static int _getIndex(final long hash, final int cap) {
return (int) ((cap - 1) & hash);
}
static final class Node {
byte[] key;
long val;
long hash;
int type = LINK;
Node next;
Node(byte[] key, long val, long hash) {
this.key = key;
this.val = val;
this.hash = hash;
}
}
public static void main(String[] args) {
Demo demo = new Demo(10000000);
for (int i = 0; i < 10000000; ++i) {
demo.put(String.valueOf(i).getBytes(StandardCharsets.UTF_8), i);
}
System.out.println("====== Hash算法检测 ======");
int emptySlotCount = 0, turnTreeCount = 0, avgLinkSize = 0;
final int cap = Demo.cap;
for (int i = 0; i < cap; ++i) {
Node head = map[i];
if (head == null) {
++emptySlotCount;
} else {
if (head.type == LINK) {
int linkSize = 1;
do {
++linkSize;
head = head.next;
} while (head != null);
if (linkSize != 8) avgLinkSize += linkSize;
} else {
++turnTreeCount;
}
}
}
System.out.println("为空概率(%): " + (1D * emptySlotCount / cap * 100) + ",空槽位数: " + emptySlotCount);
System.out.println("为链概率(%): " + (1D * (cap - turnTreeCount - emptySlotCount) / cap * 100 + ",链槽位数: " + (cap - turnTreeCount - emptySlotCount)));
System.out.println("为树概率(%): " + (1D * turnTreeCount / cap * 100) + ",树槽位数: " + turnTreeCount);
System.out.println("总数: " + cap + ", 冲突层数平均: " + (1D * avgLinkSize / (cap - turnTreeCount - emptySlotCount)));
System.out.println("====== Hash算法检测 ======");
}
}
