001package stdlib; 002 003/** 004 * An implementation of a hash table where each value has a composite key 005 * generated from 3 objects. Acts like the Java HashMap except that: 006 * <ul> 007 * <li>None of the keys or values are allowed to be null.</li> 008 * <li>None of the values are allowed to be arrays.</li> 009 * <li>It uses == rather than .equals to compare objects for equality.</li> 010 * </ul> 011 * Hack hack hack for space efficiency... 012 */ 013public class HashMap3 { 014 015 Object[] values = new Object[128]; 016 Object[] keys1 = new Object[128]; 017 Object[] keys2 = new Object[128]; 018 Object[] keys3 = new Object[128]; 019 int size=0; 020 021 public void put (Object key1, Object key2, Object key3, Object value) { 022 if (size > values.length) { 023 grow (); 024 } 025 putNoGrow (key1, key2, key3, value); 026 } 027 028 public void grow () { 029 Object[] oldValues = this.values; 030 Object[] oldKeys1 = this.keys1; 031 Object[] oldKeys2 = this.keys2; 032 Object[] oldKeys3 = this.keys3; 033 this.values = new Object[oldValues.length * 2]; 034 this.keys1 = new Object[oldValues.length * 2]; 035 this.keys2 = new Object[oldValues.length * 2]; 036 this.keys3 = new Object[oldValues.length * 2]; 037 for (int i=0; i<oldValues.length; i++) { 038 if (oldValues[i] == null) { 039 continue; 040 } else if (oldValues[i] instanceof Object[]) { 041 Object[] valuesBucket = (Object[])(oldValues[i]); 042 Object[] keys1Bucket = (Object[])(oldKeys1[i]); 043 Object[] keys2Bucket = (Object[])(oldKeys2[i]); 044 Object[] keys3Bucket = (Object[])(oldKeys3[i]); 045 for (int j=0; j<valuesBucket.length; j++) { 046 if (valuesBucket[j] == null) { 047 break; 048 } 049 putNoGrow (keys1Bucket[j], keys2Bucket[j], keys3Bucket[j], valuesBucket[j]); 050 } 051 } else { 052 putNoGrow (oldKeys1[i], oldKeys2[i], oldKeys3[i], oldValues[i]); 053 } 054 } 055 } 056 057 public void putNoGrow (Object key1, Object key2, Object key3, Object value) { 058 size++; 059 int hash = hash3 (key1, key2, key3) % values.length; 060 if (values[hash] == null) { 061 keys1[hash] = key1; 062 keys2[hash] = key2; 063 keys3[hash] = key3; 064 values[hash] = value; 065 return; 066 } else if (values[hash] instanceof Object[]) { 067 Object[] valuesBucket = (Object[])(values[hash]); 068 Object[] keys1Bucket = (Object[])(keys1[hash]); 069 Object[] keys2Bucket = (Object[])(keys2[hash]); 070 Object[] keys3Bucket = (Object[])(keys3[hash]); 071 for (int i=0; i<valuesBucket.length; i++) { 072 if (valuesBucket[i] == null) { 073 keys1Bucket[i] = key1; 074 keys2Bucket[i] = key2; 075 keys3Bucket[i] = key3; 076 valuesBucket[i] = value; 077 return; 078 } 079 } 080 Object[] newValuesBucket = new Object[valuesBucket.length * 2]; 081 Object[] newKeys1Bucket = new Object[valuesBucket.length * 2]; 082 Object[] newKeys2Bucket = new Object[valuesBucket.length * 2]; 083 Object[] newKeys3Bucket = new Object[valuesBucket.length * 2]; 084 for (int i=0; i<valuesBucket.length; i++) { 085 newValuesBucket[i] = valuesBucket[i]; 086 newKeys1Bucket[i] = keys1Bucket[i]; 087 newKeys2Bucket[i] = keys2Bucket[i]; 088 newKeys3Bucket[i] = keys3Bucket[i]; 089 } 090 newValuesBucket[valuesBucket.length] = value; 091 newKeys1Bucket[valuesBucket.length] = key1; 092 newKeys2Bucket[valuesBucket.length] = key2; 093 newKeys3Bucket[valuesBucket.length] = key3; 094 values[hash] = newValuesBucket; 095 keys1[hash] = newKeys1Bucket; 096 keys2[hash] = newKeys2Bucket; 097 keys3[hash] = newKeys3Bucket; 098 return; 099 } else { 100 values[hash] = new Object[]{ values[hash], value }; 101 keys1[hash] = new Object[]{ keys1[hash], key1 }; 102 keys2[hash] = new Object[]{ keys2[hash], key2 }; 103 keys3[hash] = new Object[]{ keys3[hash], key3 }; 104 return; 105 } 106 } 107 108 public Object get (Object key1, Object key2, Object key3) { 109 int hash = hash3 (key1, key2, key3) % values.length; 110 if (values[hash] == null) { 111 return null; 112 } else if (values[hash] instanceof Object[]) { 113 Object[] valuesBucket = (Object[])(values[hash]); 114 Object[] keys1Bucket = (Object[])(keys1[hash]); 115 Object[] keys2Bucket = (Object[])(keys2[hash]); 116 Object[] keys3Bucket = (Object[])(keys3[hash]); 117 for (int i=0; i<valuesBucket.length; i++) { 118 if (keys1Bucket[i] == key1 119 && keys2Bucket[i] == key2 120 && keys3Bucket[i] == key3) { 121 return valuesBucket[i]; 122 } 123 } 124 return null; 125 } else if (keys1[hash] == key1 126 && keys2[hash] == key2 127 && keys3[hash] == key3) { 128 return values[hash]; 129 } else { 130 return null; 131 } 132 } 133 134 public static int hash3 (Object key1, Object key2, Object key3) { 135 return key1.hashCode () + 5 * key2.hashCode () + 13 * key3.hashCode (); 136 } 137 138}