HashTable实现

Question

我一直在尝试用Java实现Hash函数，下面是我想出的。我只想就这项工作征求意见。是否有更好的方法或对此代码进行任何改进？

HashTable.java :基本上包含创建表、添加节点和检索节点的所有可维护的函数

import java.math.BigInteger;

public class HashMap {
      // Srtting table size to a max of 32, value used to modulus for hash value.
      private final static int TABLE_SIZE = 32;

      HashEntry[] table;

      HashMap() {
            table = new HashEntry[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = null;
      }

      /* function to retrieve value from the table according to key */
      public int get(String key) {
            int hash = new BigInteger(toAscii(key)).mod(new BigInteger(((Integer)TABLE_SIZE).toString())).intValue();
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] == null)
                  return -1;
            else
                  return table[hash].getValue();
      }

      /* function to add value to the table */
      public void put(String key, int value) {
            //creating hash code using key value given as a string
            int hash = new BigInteger(toAscii(key)).mod(new BigInteger(((Integer)TABLE_SIZE).toString())).intValue();
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            table[hash] = new HashEntry(key, value);
      }

      /* value to create the Hash code from he name entered, basically converting name to ASCII */
      public static String toAscii(String s){
          StringBuilder sb = new StringBuilder();
          long asciiInt;
          // loop through all values in the string, including blanks
          for (int i = 0; i < s.length(); i++){
              //getting Ascii value of character and adding it to the string.
              char c = s.charAt(i);
              asciiInt = (int)c; 
              sb.append(asciiInt);
          }
          return String.valueOf(sb);
  }
}

HashEntry.java:接受条目的对象包含setter和getter

public class HashEntry {
      private String key;
      private int value;

      HashEntry(String key, int value) {
            this.key = key;
            this.value = value;
      }     

      public String getKey() {
            return key;
      }

      public int getValue() {
            return value;
      }
}

HasheTable.java:只是测试我的实现

import java.io.IOException;


public class HashTable {
    public static void main(String[] args) throws IOException
    {
        HashMap entry = new HashMap();
        entry.put("Wasif", 36100);
        entry.put("Stephen Hughes", 22100);
        System.out.println(entry.get("Stephen Hughes"));
    }
}

Answer 1

实现哈希表

这个哈希表实现有点有限:它只支持字符串键和int值。把它概括一下就好了。

当获得不在表中的键的值时，常见的预期行为是null。因为您使用int作为值的类型，所以这是不可能的，但是-1似乎不够特殊，无法被普遍理解为“缺失值”。

toAscii方法非常糟糕：

• 它只在内部使用，所以不应该公开
• 名称没有很好地描述它所做的事情:将字符串转换为ascii听起来更像是编码转换，而不是哈希代码计算。最好叫它calculateHashCode，然后让它返回一个BigInteger
• 更好的做法是使用字符串本身的hashCode，而不是重新实现您自己的

命名

HashMap entry = new HashMap();

“条目”是地图的不恰当名称。“地图”似乎是显而易见的选择。

通用编码问题

HashEntry类是哈希表的实现细节。因此，最好将该类隐藏在哈希表中，使其成为private static class。

而不是这样：

新BigInteger(整数)TABLE_SIZE).toString())；

一种更好、更简单的方法：

BigInteger.valueOf(TABLE_SIZE);

将变量限制在尽可能小的范围内，以防止意外更改超出其预期目的。例如，在此代码中：

long asciiInt; // loop through all values in the string, including blanks for (int i = 0; i < s.length(); i++){ //getting Ascii value of character and adding it to the string. char c = s.charAt(i); asciiInt = (int)c; sb.append(asciiInt); }

asciiInt应该在循环中声明。

这段代码看起来非常混乱:您得到一个char，将它转换为一个int来存储在一个long变量中。这可以简单地说：

    for (int i = 0; i < s.length(); i++){
        sb.append((int) s.charAt(i));
    }

更简单的是使用for-each循环：

    for (char c : s.toCharArray()) {
        sb.append((int) c);
    }

table = new HashEntry[TABLE\_SIZE]; for (int i = 0; i < TABLE\_SIZE; i++) table[i] = null;

当迭代数组的所有元素时，我建议使用数组的长度作为限制。这更安全。如下所示：

        table = new HashEntry[TABLE_SIZE];
        for (int i = 0; i < table.length; i++) { ... }

但是，由于只使用这个循环将值赋值给null，所以整个循环没有意义，所以可以安全地删除它。

当您使用!=对对象进行比较时，这是非常可疑的，就像对代码中的键所做的那样：

while (table[hash] != null && table[hash].getKey() != key) hash = (hash + 1) % TABLE\_SIZE;

例如，您认为这段代码会打印什么：

    String key1 = new String("Jack");
    String key2 = new String("Jack");
    entry.put(key1, 11);
    entry.put(key2, 21);
    System.out.println(entry.get(key1));
    System.out.println(entry.get(key2));

它将打印11和21。我建议在所有对象上用!=替换.equals(...)。然后，这两个键将被认为是相等的，就像通常从散列映射中期望的那样，而print语句将返回21和21。

其他编码风格问题

• 我建议即使对单语句块也使用大括号{ ... }。
• 与像/* function to retrieve value from the table according to key */这样的注释不同，使用正确的JavaDoc，例如:根据键** @param键从表中检索值**@param键查找*@返回键的值，或者如果不存在则为null */
• 因为HashEntry的字段永远不会改变，所以您可以使它们成为final
• 此代码块出现两次: This (table哈希 != null && !table哈希.getKey().equals(key))散列=(散列+ 1) % TABLE_SIZE；避免代码重复。提取到私有助手方法，或以不必重复代码的方式重构实现。此代码的相同注意事项: int散列=新的BigInteger(((Integer)TABLE_SIZE).toString())).intValue()；(toAscii(Key)).mod(新的

改进的实现

根据上述一些建议，可以简化和改进执行工作：

private int calculateHashCode(String key) {
    int mod = key.hashCode() % TABLE_SIZE;
    return mod < 0 ? mod + TABLE_SIZE : mod;
}

private int findIndex(String key) {
    int index = calculateHashCode(key);
    while (table[index] != null && !table[index].getKey().equals(key)) {
        index = (index + 1) % TABLE_SIZE;
    }
    return index;
}

public int get(String key) {
    int index = findIndex(key);
    return table[index] == null ? -1 : table[index].getValue();
}

public void put(String key, int value) {
    table[findIndex(key)] = new HashEntry(key, value);
}