0

我正在为分配实现自己的 HashTable，我需要从文本文件中读取，然后将其内容添加到 HashTable。我遇到了几个问题，

1) 字符串的一些哈希值以负数出现。

2）有些词没有被添加。

这是我的哈希函数代码：

   public int hash(String key) {
        int hashkey = key.hashCode();

        return hashkey % arraySize;
    } // END hash()

对于computer它返回整数的单词-97，为了解决这个问题，我包含了一个 if 语句，如果整数为负数则使其为正数。但是，即使有这个词computer，也不会在 index 处添加到我的 HashTable 中97。

其他一些没有被添加的词是：tree, subtree, record, single除其他外。这是我的文件 I/O 函数并将它们添加到哈希表中：

public static void readParagraph() {
    BufferedReader reader;
    String inputLine;

    try {
        reader = new BufferedReader(new FileReader(".\\src\\paragraph.txt"));
        while((inputLine = reader.readLine()) != null) {
            String[] strings = inputLine.split("(\\s|\\p{Punct})+");
            insertParagraph(strings);
        }
    } catch (IOException e) {
        System.out.println("Error: " + e);
    }
} // END readParagraph()

private static void insertParagraph(String[] strings) {
    Link link;
    for (String string : strings) {
        if (!string.equals("")) {
            link = new Link(string.replaceAll("[^a-zA-Z'\\s]", "").toLowerCase());
            paragraph.insert(link);
        }
    }
} // END insertParagraph()

有谁知道为什么没有添加一些单词有什么问题？或者为什么我得到哈希值的负数？

编辑：更多信息

public class A4Q3 {
    static HashTable dictionary = new HashTable(1009);
    static HashTable paragraph = new HashTable(164);
    public static void main(String[] args) {
        readParagraph();
        paragraph.displayTable();
        System.out.println();
        System.out.println(paragraph.wordCount);
    } // END main()

    public void insert(Link link) {
        String key = link.getKey();
        Link previous = null;
        Link current = first;

        while(current != null && key.compareTo(current.getKey()) > 0) {
            previous = current;
            current = current.getNext();
        }

        if(previous == null) {
            first = link;
        } else {
            previous.setNext(link);
            link.setNext(current);
        }
    } // END insert()

链接类：

public class Link {
private String data;
private Link next;

public Link(String data) {
    this.data = data;
} // END Link()

public String getKey() {
    return data;
} // END getKey()

public void displayLink() {
    System.out.print(data + " ");
} // END displayLink()

public Link getNext() {
    return next;
} // END getNext()

public void setNext(Link next) {
    this.next = next;
} // END setNext()

} // 结束链接

4

1 回答 1

2

您没有正确处理负哈希码：

   public int hash(String key) 
   {
        int hashkey = key.hashCode();

        return hashkey % arraySize;
   }

正如你所说，如果hashkey是负面的，你有问题，所以你能做的就是改变你的hash功能。

哈希码修复：

   public int hash(String key) 
   {
        int hashkey = key.hashCode();

        return (hashkey & 0x7FFFFFFF) % arraySize;
   }

这将执行一个bitwise andwith hashkeyand 0x7FFFFFFF，它是31 个 1 的十六进制，即：

01111111 11111111 11111111 11111111

因此，它会将任何输入转换为正数，因为除了最重要的数字之外，每个数字都bitwise and将带有 1。由于 java 使用二进制补码，因此使用了最重要的数字来指示标志。由于为 0，因此该值现在将始终为正。andhashkeyand0 & 1

您得到的哈希值为负的原因String是因为hashCode()for String。

String 为负哈希值的原因：

public int  hashCode() 
{
        int h = hash;

        if (h == 0) 
        {
            int off = offset;
            char val[] = value;
            int len = count;

            for (int i = 0; i < len; i++) 
            {
                h = 31*h + val[off++];
            }

            hash = h;
        }

        return h;
    }

请注意，您的源代码可能不一样，但是，负数的原因是。如果h变得大于Integer.MAX_VALUE，它将环绕到Integer.MIN_VALUE，即：

Integer.MAX_VALUE + 1 == Integer.MIN_VALUE
于 2013-07-15T17:06:45.990 回答