FastByIdMap是基于散列的。在处理冲突时是线性探測而非分离链接,这样就不必为每个条目添加一个Map.Entry对象。从而节省内存开销。
以下代码是一个线性探測Map的Demo:
package com.example.mahout;public class ArrayHashST_Linear_Probing<Key, Val> {
private int M = 30001;
private Key[] keys = (Key[]) new Object[M];
private Val[] vals = (Val[]) new Object[M]; private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
} public void put(Key key, Val val) {
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % M)
if (keys[i].equals(key))
break;
keys[i] = key;
vals[i] = val;
} public Val get(Key key) {
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % M)
if (keys[i].equals(key))
break;
return vals[i];
} public static void main(String[] args) { ArrayHashST_Linear_Probing<String,String> st = new ArrayHashST_Linear_Probing<String, String>();
st.put("jocularly", "jocularly");
st.put("seriously", "seriously");
st.put("listen", "listen");
st.put("suburban", "suburban");
st.put("untravelled", "untravelled");
st.put("considerating", "considerating");
st.put("browsing","browsing");
System.out.println(st.get("jocularly")); }}
这个是分离链接的Demo:
package com.example.mahout;public class ListHashST_Separate_Chaining<Key, Value> {
private int M = 8191;
private Node[] st = new Node[M]; private static class Node {
Object key;
Object val;
Node next; Node(Object key, Object val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
} private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
} public void put(Key key, Value val) {
int i = hash(key);
for (Node x = st[i]; x != null; x = x.next) {
if (key.equals(x.key)) {
x.val = val;
return;
}
}
st[i] = new Node(key, val, st[i]);
} public Value get(Key key) {
int i = hash(key);
//System.out.println(i);
for (Node x = st[i]; x != null; x = x.next){
System.out.println(x.val);
if (key.equals(x.key))
return (Value) x.val; } return null;
} public static void main(String[] args) {
// TODO Auto-generated method stub
ListHashST_Separate_Chaining<String, String> st = new ListHashST_Separate_Chaining<String, String>();
st.put("jocularly", "jocularly");
st.put("seriously", "seriously");
st.put("listen", "listen");
st.put("suburban", "suburban");
st.put("untravelled", "untravelled");
st.put("considerating", "considerating");
st.put("browsing","browsing");
st.get("jocularly");
//System.out.println(st.get("jocularly")); }}