i'm implementing own hashtable assignment, , need read text file, add contents hashtable. there couple of problems have run into,
1) hash values strings coming out negative numbers.
2) words not being added.
here's code hash function:
public int hash(string key) { int hashkey = key.hashcode(); return hashkey % arraysize; } // end hash() for word computer returns integer -97, around included if statement make positive if integer negative. however, word computer, not added hashtable @ index 97.
some other words not added are: tree, subtree, record, single among others. here functions file i/o , adding them hashtable:
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; (string string : strings) { if (!string.equals("")) { link = new link(string.replaceall("[^a-za-z'\\s]", "").tolowercase()); paragraph.insert(link); } } } // end insertparagraph() does know wrong why words not being added? or why getting negative numbers hash values?
edit: more information
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() link class:
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() } // end link
you're not handling negative hash codes properly:
public int hash(string key) { int hashkey = key.hashcode(); return hashkey % arraysize; } as said, if hashkey negative, have issues, can change hash function.
hash-code fix:
public int hash(string key) { int hashkey = key.hashcode(); return (hashkey & 0x7fffffff) % arraysize; } this perform bitwise and hashkey , 0x7fffffff, hexadecimal 31 1's, ie:
01111111 11111111 11111111 11111111
so, turn input positive number, because bitwise and and every digit in hashkey 1, except most-significant digit, and 0. since java uses two's complement, most-significant digit used indicate sign. since 0 & 1 0, value positive.
the reason you're getting negative values hashes of string because of hashcode() string.
reason negative hash values string:
public int hashcode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; (int = 0; < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; } note source code may not same, nonetheless, reason negative numbers is. if h becomes greater integer.max_value, wrap around integer.min_value, ie:
integer.max_value + 1 == integer.min_value 
Comments
Post a Comment