आप संभवतः द्वारा स्मृति पर एक छोटे से बचा सकते हैं:
(क) एक मजबूत, व्यापक उपयोग करते हुए हैश कोड, और इस प्रकार कुंजी स्टोर करने से परहेज करते हुए;
(बी) खुद को एक सरणी से आवंटित करके, प्रति हैश तालिका प्रविष्टि पर एक अलग ऑब्जेक्ट बनाने से परहेज करें।
यदि यह उपयोगी है, तो संख्यात्मक प्राप्तकर्ता हैश तालिका का कोई भी फ्रिल्स जावा कार्यान्वयन नहीं है जिसे मैंने कभी-कभी उपयोगी पाया है। आप सीधे CharSequence (स्ट्रिंग समेत) पर कुंजी कर सकते हैं, अन्यथा आपको अपने ऑब्जेक्ट्स के लिए एक मजबूत-आश 64-बिट हैश फ़ंक्शन के साथ आना चाहिए।
याद रखें, यह कार्यान्वयन कुंजी को स्टोर नहीं करता है, इसलिए यदि दो आइटमों में एक ही हैश कोड है (जिसे आप 2^32 या दो बिलियन आइटम के क्रम में हैशिंग के बाद उम्मीद करेंगे एक अच्छा हैश फ़ंक्शन), फिर एक आइटम दूसरे को ओवरराइट करेगा:
public class CompactMap<E> implements Serializable {
static final long serialVersionUID = 1L;
private static final int MAX_HASH_TABLE_SIZE = 1 << 24;
private static final int MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR = 1 << 20;
private static final long[] byteTable;
private static final long HSTART = 0xBB40E64DA205B064L;
private static final long HMULT = 7664345821815920749L;
static {
byteTable = new long[256];
long h = 0x544B2FBACAAF1684L;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 31; j++) {
h = (h >>> 7)^h;
h = (h << 11)^h;
h = (h >>> 10)^h;
}
byteTable[i] = h;
}
}
private int maxValues;
private int[] table;
private int[] nextPtrs;
private long[] hashValues;
private E[] elements;
private int nextHashValuePos;
private int hashMask;
private int size;
@SuppressWarnings("unchecked")
public CompactMap(int maxElements) {
int sz = 128;
int desiredTableSize = maxElements;
if (desiredTableSize < MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR) {
desiredTableSize = desiredTableSize * 4/3;
}
desiredTableSize = Math.min(desiredTableSize, MAX_HASH_TABLE_SIZE);
while (sz < desiredTableSize) {
sz <<= 1;
}
this.maxValues = maxElements;
this.table = new int[sz];
this.nextPtrs = new int[maxValues];
this.hashValues = new long[maxValues];
this.elements = (E[]) new Object[sz];
Arrays.fill(table, -1);
this.hashMask = sz-1;
}
public int size() {
return size;
}
public E put(CharSequence key, E val) {
return put(hash(key), val);
}
public E put(long hash, E val) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
int lastk;
do {
if (hashValues[k] == hash) {
E old = elements[k];
elements[k] = val;
return old;
}
lastk = k;
k = nextPtrs[k];
} while (k != -1);
k = nextHashValuePos++;
nextPtrs[lastk] = k;
} else {
k = nextHashValuePos++;
table[hc] = k;
}
if (k >= maxValues) {
throw new IllegalStateException("Hash table full (size " + size + ", k " + k);
}
hashValues[k] = hash;
nextPtrs[k] = -1;
elements[k] = val;
size++;
return null;
}
public E get(long hash) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
do {
if (hashValues[k] == hash) {
return elements[k];
}
k = nextPtrs[k];
} while (k != -1);
}
return null;
}
public E get(CharSequence hash) {
return get(hash(hash));
}
public static long hash(CharSequence cs) {
if (cs == null) return 1L;
long h = HSTART;
final long hmult = HMULT;
final long[] ht = byteTable;
for (int i = cs.length()-1; i >= 0; i--) {
char ch = cs.charAt(i);
h = (h * hmult)^ht[ch & 0xff];
h = (h * hmult)^ht[(ch >>> 8) & 0xff];
}
return h;
}
}
स्रोत
2009-05-15 02:36:42
संचालन किस तरह धीमा करने के लिए कर रहे हैं, प्रविष्टि या देखने या यात्रा? आपको अपने संग्रहों के साथ क्या करने की ज़रूरत है, वस्तुओं को पुनर्प्राप्त करें या उन्हें ऑर्डर करें या जांचें कि क्या वे संग्रह में निहित हैं या नहीं? क्या आपको सभी वस्तुओं को स्मृति में रखने की आवश्यकता है या नहीं? – pgras
यह मुझे भी रूचि देता है ... धीमा क्या है और क्यों? यदि हैशकोड और बराबर हैं तो मानचित्र/सेट आमतौर पर बहुत तेज़ होते हैं। क्या आपका हैशकोड अलग और अद्वितीय है? – ReneS
मैं लगभग पूरी तरह से() संचालन करता हूं। हैशसेट वास्तव में आमतौर पर ठीक है; यह है कि मेरे पास बहुत से सेट हैं, और लाखों मिलते हैं() एस। स्मृति या गति में 1% लाभ भी ढूंढना सार्थक होगा। निश्चित रूप से मैं बस() कम करने, या सेट को छीनने के तरीकों को देखता हूं। –