Skip to content

Instantly share code, notes, and snippets.

@dzaima
Last active Nov 24, 2021
Embed
What would you like to do?
import java.util.*;
import static java.lang.String.format;
@SuppressWarnings("unchecked")
public class LProbSOAMap<K, V> implements Map<K,V> {
private static final double DEFAULT_MAX_LOAD_FACTOR = 0.6;
private static final double DEFAULT_MIN_LOAD_FACTOR = DEFAULT_MAX_LOAD_FACTOR / 4;
private static final int DEFAULT_MAP_CAPACITY_POW_2 = 6;
private int size = 0;
private int tombstones = 0;
private int capPow2 = DEFAULT_MAP_CAPACITY_POW_2;
public K[] bucketsK = (K[]) new Object[1<<DEFAULT_MAP_CAPACITY_POW_2];
public V[] bucketsV = (V[]) new Object[1<<DEFAULT_MAP_CAPACITY_POW_2];
public int[] bucketsH = new int[1<<DEFAULT_MAP_CAPACITY_POW_2]; // k=null: hash=0 - empty; hash=1 - tombstone
/**
* A method that mixes even further the bits of the resulting obj.hashCode().
* Inspired by the Murmur Hash mixer (finalizer).
*
* @param obj The object for which we are computing the hashcode
* @return The hashcode of the object.
*/
public static int hash(final Object obj) {
int h = obj.hashCode();
h ^= h >> 16;
h *= 0x3243f6a9;
h ^= h >> 16;
return h & 0xfffffff;
}
protected final void reHashElements(int capModifier) {
this.capPow2+=capModifier;
K[] oldBucketsK = this.bucketsK;
V[] oldBucketsV = this.bucketsV;
int[] oldBucketsH = this.bucketsH;
this.bucketsK = (K[]) new Object[1 << capPow2];
this.bucketsV = (V[]) new Object[1 << capPow2];
this.bucketsH = new int[1 << capPow2];
this.size = 0;
this.tombstones = 0;
for (int i = 0; i < oldBucketsK.length; ++i) {
if (oldBucketsK[i] != null) {
this.put(oldBucketsK[i], oldBucketsV[i], oldBucketsH[i]);
}
}
}
protected final void increaseCapacity() {
final double lf = (double)(size+tombstones) / bucketsK.length;
if (lf > DEFAULT_MAX_LOAD_FACTOR) {
reHashElements(1);
}
}
protected final void decreaseCapacity() {
final double lf = (double)(size) / bucketsK.length;
if (lf < DEFAULT_MIN_LOAD_FACTOR && this.capPow2 > DEFAULT_MAP_CAPACITY_POW_2) {
reHashElements(-1);
}
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
@Override
public boolean containsKey(Object key) {
return get(key)!=null;
}
@Override
public boolean containsValue(Object value) {
for(int i = 0; i < bucketsK.length; i++) {
if (value.equals(bucketsV[i])) {
return true;
}
}
return false;
}
public V get(Object key) {
int hash = hash(key);
int idx = hash & (bucketsK.length-1);
int bucketH = bucketsH[idx];
K bucketK = bucketsK[idx];
if (bucketK==null && bucketH==0) {
return null;
}
do {
if (bucketH == hash && key.equals(bucketK)) {
return bucketsV[idx];
}
idx++;
if (idx==bucketsK.length) idx = 0;
bucketK = bucketsK[idx];
bucketH = bucketsH[idx];
} while(!(bucketK==null && bucketH==0));
return null;
}
protected V put(K key, V value, int hash) {
// We increase capacity if it's needed
increaseCapacity();
// We calculate the base bucket for the entry
int idx = hash & (bucketsK.length-1);
while(true) {
// If the slot is either empty or a tombstone, we insert the new item
if (bucketsK[idx] == null) {
bucketsK[idx] = key;
bucketsV[idx] = value;
bucketsH[idx] = hash;
size++;
// No value was updated so we return null
return null;
}
else if (bucketsH[idx] == hash && key.equals(bucketsK[idx])) {
// The element already existed in the map
// We keep the old value to return it later
// We update the element to new value
V ret;
ret = bucketsV[idx];
bucketsV[idx] = value;
// We return the value that was replaced
return ret;
}
idx++;
if (bucketsK.length==idx) idx = 0;
}
}
@Override
public V put(K key, V value) {
if (null==key) {
throw new IllegalArgumentException("Map doesn't support null keys");
}
return put(key, value, hash(key));
}
@Override
public V remove(Object key) {
int hash = hash(key);
int idx = hash & (bucketsK.length-1);
if (null==bucketsK[idx] && 0==bucketsH[idx]) {
return null;
}
do {
if (bucketsH[idx] == hash && key.equals(bucketsK[idx])) {
V oldVal = bucketsV[idx];
bucketsK[idx] = null;
bucketsV[idx] = null;
bucketsH[idx] = 1;
tombstones++;
size--;
return oldVal;
}
idx++;
if (idx == bucketsK.length) idx = 0;
} while (!(null==bucketsK[idx] && 0==bucketsH[idx]));
decreaseCapacity();
return null;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for(var e : m.entrySet()) {
put(e.getKey(), e.getValue());
}
}
@Override
public void clear() {
bucketsK = (K[]) new Object[1<<DEFAULT_MAP_CAPACITY_POW_2];
bucketsV = (V[]) new Object[1<<DEFAULT_MAP_CAPACITY_POW_2];
bucketsH = new int[1<<DEFAULT_MAP_CAPACITY_POW_2];
}
@Override
public Set<K> keySet() {
HashSet<K> result = new HashSet<>();
for(int i = 0; i < bucketsK.length; i++) {
if (bucketsK[i]!=null) {
result.add(bucketsK[i]);
}
}
return result;
}
@Override
public Collection<V> values() {
HashSet<V> result = new HashSet<>();
for(int i = 0; i < bucketsK.length; i++) {
if (bucketsK[i]!=null) {
result.add(bucketsV[i]);
}
}
return result;
}
@Override
public Set<Map.Entry<K, V>> entrySet() {
HashSet<Map.Entry<K, V>> result = new HashSet<>();
for(int i = 0; i < bucketsK.length; i++) {
if (bucketsK[i]!=null) {
result.add(new LProbArrMapEntry(bucketsK[i], bucketsV[i]));
}
}
return result;
}
@Override
public String toString() {
StringBuilder buff = new StringBuilder();
for(int i = 0; i < bucketsK.length; ++i) {
buff.append(format("bucket[%d] = ", i));
if (null == bucketsK[i]) {
buff.append(bucketsH[i]==0? "NULL\n" : "TOMBSTONE\n");
} else {
buff.append(format(" {hash=%d, key=%s, value=%s }\n",
bucketsH[i], bucketsK[i], bucketsV[i]));
}
}
return buff.toString();
}
protected static class LProbArrMapEntry<K, V> implements Map.Entry<K, V> { // exists only for entrySet
public K key;
public V value;
public LProbArrMapEntry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "OaEntry{" +
"key=" + key +
", val=" + value +
'}';
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
throw new RuntimeException("LProbArrMapEntry.setValue not supported!");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment