duke@1: * The current set of methods is: duke@1: *
getKey(String) method can be used to use the selected hash
duke@1: * method to produce a key. The method string will contain
duke@1: * "length()", "charAt(n)", or "hashCode()", and is intended for use by
duke@1: * code generators.
duke@1: *
duke@1: * The keys array will contain the full set of unique keys.
duke@1: *
duke@1: * The buckets array will contain a set of arrays, one for
duke@1: * each key in the keys, where buckets[x][y]
duke@1: * is an index into the strings array.
duke@1: * @author Bryan Atsatt
duke@1: */
duke@1: public class StaticStringsHash {
duke@1:
duke@1: /** The set of strings upon which the hash info is created */
duke@1: public String[] strings = null;
duke@1:
duke@1: /** Unique hash keys */
duke@1: public int[] keys = null;
duke@1:
duke@1: /** Buckets for each key, where buckets[x][y] is an index
duke@1: * into the strings[] array. */
duke@1: public int[][] buckets = null;
duke@1:
duke@1: /** The method to invoke on String to produce the hash key */
duke@1: public String method = null;
duke@1:
duke@1: /** Get a key for the given string using the
duke@1: * selected hash method.
duke@1: * @param str the string to return a key for.
duke@1: * @return the key.
duke@1: */
duke@1: public int getKey(String str) {
duke@1: switch (keyKind) {
duke@1: case LENGTH: return str.length();
duke@1: case CHAR_AT: return str.charAt(charAt);
duke@1: case HASH_CODE: return str.hashCode();
duke@1: }
duke@1: throw new Error("Bad keyKind");
duke@1: }
duke@1:
duke@1: /** Constructor
duke@1: * @param strings the set of strings upon which to
duke@1: * find an optimal hash method. Must not contain
duke@1: * duplicates.
duke@1: */
duke@1: public StaticStringsHash(String[] strings) {
duke@1: this.strings = strings;
duke@1: length = strings.length;
duke@1: tempKeys = new int[length];
duke@1: bucketSizes = new int[length];
duke@1: setMinStringLength();
duke@1:
duke@1: // Decide on the best algorithm based on
duke@1: // which one has the smallest maximum
duke@1: // bucket depth. First, try length()...
duke@1:
duke@1: int currentMaxDepth = getKeys(LENGTH);
duke@1: int useCharAt = -1;
duke@1: boolean useHashCode = false;
duke@1:
duke@1: if (currentMaxDepth > 1) {
duke@1:
duke@1: // At least one bucket had more than one
duke@1: // entry, so try charAt(i). If there
duke@1: // are a lot of strings in the array,
duke@1: // and minStringLength is large, limit
duke@1: // the search to a smaller number of
duke@1: // characters to avoid spending a lot
duke@1: // of time here that is most likely to
duke@1: // be pointless...
duke@1:
duke@1: int minLength = minStringLength;
duke@1: if (length > CHAR_AT_MAX_LINES &&
duke@1: length * minLength > CHAR_AT_MAX_CHARS) {
duke@1: minLength = length/CHAR_AT_MAX_CHARS;
duke@1: }
duke@1:
duke@1: charAt = 0;
duke@1: for (int i = 0; i < minLength; i++) {
duke@1: int charAtDepth = getKeys(CHAR_AT);
duke@1: if (charAtDepth < currentMaxDepth) {
duke@1: currentMaxDepth = charAtDepth;
duke@1: useCharAt = i;
duke@1: if (currentMaxDepth == 1) {
duke@1: break;
duke@1: }
duke@1: }
duke@1: charAt++;
duke@1: }
duke@1: charAt = useCharAt;
duke@1:
duke@1:
duke@1: if (currentMaxDepth > 1) {
duke@1:
duke@1: // At least one bucket had more than one
duke@1: // entry, try hashCode().
duke@1: //
duke@1: // Since the cost of computing a full hashCode
duke@1: // (for the runtime target string) is much higher
duke@1: // than the previous methods, use it only if it is
duke@1: // substantially better. The definition of 'substantial'
duke@1: // here is not very well founded, and could be improved
duke@1: // with some further analysis ;^)
duke@1:
duke@1: int hashCodeDepth = getKeys(HASH_CODE);
duke@1: if (hashCodeDepth < currentMaxDepth-3) {
duke@1:
duke@1: // Using the full hashCode results in at least
duke@1: // 3 fewer entries in the worst bucket, so will
duke@1: // therefore avoid at least 3 calls to equals()
duke@1: // in the worst case.
duke@1: //
duke@1: // Note that using a number smaller than 3 could
duke@1: // result in using a hashCode when there are only
duke@1: // 2 strings in the array, and that would surely
duke@1: // be a poor performance choice.
duke@1:
duke@1: useHashCode = true;
duke@1: }
duke@1: }
duke@1:
duke@1: // Reset keys if needed...
duke@1:
duke@1: if (!useHashCode) {
duke@1: if (useCharAt >= 0) {
duke@1:
duke@1: // Use the charAt(i) method...
duke@1:
duke@1: getKeys(CHAR_AT);
duke@1:
duke@1: } else {
duke@1:
duke@1: // Use length method...
duke@1:
duke@1: getKeys(LENGTH);
duke@1: }
duke@1: }
duke@1: }
duke@1:
duke@1: // Now allocate and fill our real hashKeys array...
duke@1:
duke@1: keys = new int[bucketCount];
duke@1: System.arraycopy(tempKeys,0,keys,0,bucketCount);
duke@1:
duke@1: // Sort keys and bucketSizes arrays...
duke@1:
duke@1: boolean didSwap;
duke@1: do {
duke@1: didSwap = false;
duke@1: for (int i = 0; i < bucketCount - 1; i++) {
duke@1: if (keys[i] > keys[i+1]) {
duke@1: int temp = keys[i];
duke@1: keys[i] = keys[i+1];
duke@1: keys[i+1] = temp;
duke@1: temp = bucketSizes[i];
duke@1: bucketSizes[i] = bucketSizes[i+1];
duke@1: bucketSizes[i+1] = temp;
duke@1: didSwap = true;
duke@1: }
duke@1: }
duke@1: }
duke@1: while (didSwap == true);
duke@1:
duke@1: // Allocate our buckets array. Fill the string
duke@1: // index slot with an unused key so we can
duke@1: // determine which are free...
duke@1:
duke@1: int unused = findUnusedKey();
duke@1: buckets = new int[bucketCount][];
duke@1: for (int i = 0; i < bucketCount; i++) {
duke@1: buckets[i] = new int[bucketSizes[i]];
duke@1: for (int j = 0; j < bucketSizes[i]; j++) {
duke@1: buckets[i][j] = unused;
duke@1: }
duke@1: }
duke@1:
duke@1: // And fill it in...
duke@1:
duke@1: for(int i = 0; i < strings.length; i++) {
duke@1: int key = getKey(strings[i]);
duke@1: for (int j = 0; j < bucketCount; j++) {
duke@1: if (keys[j] == key) {
duke@1: int k = 0;
duke@1: while (buckets[j][k] != unused) {
duke@1: k++;
duke@1: }
duke@1: buckets[j][k] = i;
duke@1: break;
duke@1: }
duke@1: }
duke@1: }
duke@1: }
duke@1:
duke@1: /** Print an optimized 'contains' method for the
duke@1: * argument strings
duke@1: */
duke@1: public static void main (String[] args) {
duke@1: StaticStringsHash hash = new StaticStringsHash(args);
duke@1: System.out.println();
duke@1: System.out.println(" public boolean contains(String key) {");
duke@1: System.out.println(" switch (key."+hash.method+") {");
duke@1: for (int i = 0; i < hash.buckets.length; i++) {
duke@1: System.out.println(" case "+hash.keys[i]+": ");
duke@1: for (int j = 0; j < hash.buckets[i].length; j++) {
duke@1: if (j > 0) {
duke@1: System.out.print(" } else ");
duke@1: } else {
duke@1: System.out.print(" ");
duke@1: }
duke@1: System.out.println("if (key.equals(\""+ hash.strings[hash.buckets[i][j]] +"\")) {");
duke@1: System.out.println(" return true;");
duke@1: }
duke@1: System.out.println(" }");
duke@1: }
duke@1: System.out.println(" }");
duke@1: System.out.println(" return false;");
duke@1: System.out.println(" }");
duke@1: }
duke@1:
duke@1: private int length;
duke@1: private int[] tempKeys;
duke@1: private int[] bucketSizes;
duke@1: private int bucketCount;
duke@1: private int maxDepth;
duke@1: private int minStringLength = Integer.MAX_VALUE;
duke@1: private int keyKind;
duke@1: private int charAt;
duke@1:
duke@1: private static final int LENGTH = 0;
duke@1: private static final int CHAR_AT = 1;
duke@1: private static final int HASH_CODE = 2;
duke@1:
duke@1: /* Determines the maximum number of charAt(i)
duke@1: * tests that will be done. The search is
duke@1: * limited because if the number of characters
duke@1: * is large enough, the likelyhood of finding
duke@1: * a good hash key based on this method is
duke@1: * low. The CHAR_AT_MAX_CHARS limit only
duke@1: * applies f there are more strings than
duke@1: * CHAR_AT_MAX_LINES.
duke@1: */
duke@1: private static final int CHAR_AT_MAX_LINES = 50;
duke@1: private static final int CHAR_AT_MAX_CHARS = 1000;
duke@1:
duke@1: private void resetKeys(int keyKind) {
duke@1: this.keyKind = keyKind;
duke@1: switch (keyKind) {
duke@1: case LENGTH: method = "length()"; break;
duke@1: case CHAR_AT: method = "charAt("+charAt+")"; break;
duke@1: case HASH_CODE: method = "hashCode()"; break;
duke@1: }
duke@1: maxDepth = 1;
duke@1: bucketCount = 0;
duke@1: for (int i = 0; i < length; i++) {
duke@1: tempKeys[i] = 0;
duke@1: bucketSizes[i] = 0;
duke@1: }
duke@1: }
duke@1:
duke@1: private void setMinStringLength() {
duke@1: for (int i = 0; i < length; i++) {
duke@1: if (strings[i].length() < minStringLength) {
duke@1: minStringLength = strings[i].length();
duke@1: }
duke@1: }
duke@1: }
duke@1:
duke@1: private int findUnusedKey() {
duke@1: int unused = 0;
duke@1: int keysLength = keys.length;
duke@1:
duke@1: // Note that we just assume that resource
duke@1: // exhaustion will occur rather than an
duke@1: // infinite loop here if the set of keys
duke@1: // is very large.
duke@1:
duke@1: while (true) {
duke@1: boolean match = false;
duke@1: for (int i = 0; i < keysLength; i++) {
duke@1: if (keys[i] == unused) {
duke@1: match = true;
duke@1: break;
duke@1: }
duke@1: }
duke@1: if (match) {
duke@1: unused--;
duke@1: } else {
duke@1: break;
duke@1: }
duke@1: }
duke@1: return unused;
duke@1: }
duke@1:
duke@1: private int getKeys(int methodKind) {
duke@1: resetKeys(methodKind);
duke@1: for(int i = 0; i < strings.length; i++) {
duke@1: addKey(getKey(strings[i]));
duke@1: }
duke@1: return maxDepth;
duke@1: }
duke@1:
duke@1: private void addKey(int key) {
duke@1:
duke@1: // Have we seen this one before?
duke@1:
duke@1: boolean addIt = true;
duke@1: for (int j = 0; j < bucketCount; j++) {
duke@1: if (tempKeys[j] == key) {
duke@1: addIt = false;
duke@1: bucketSizes[j]++;
duke@1: if (bucketSizes[j] > maxDepth) {
duke@1: maxDepth = bucketSizes[j];
duke@1: }
duke@1: break;
duke@1: }
duke@1: }
duke@1:
duke@1: if (addIt) {
duke@1: tempKeys[bucketCount] = key;
duke@1: bucketSizes[bucketCount] = 1;
duke@1: bucketCount++;
duke@1: }
duke@1: }
duke@1: }