hash.java를 이용한 rehash() method 를 짜라하는데 아무런 감이 없네요. 어찌해야할지. insert() 로 불려져야하고 (인수가 0.5를 넘을때마다 전체 해쉬테이블을 두배정도큰 array 로 움직이게 하기위해서). 새로운 array size는 소수 (2,3,5,7,11,13,17,,,,,)야 합니다. 그리고 delete된 아이템도 다뤄야 한다네요 (-1보다 큰)
이해도 잘안가고 미치겠네요.. 좀 도와주세요...
원래 질문입니다.(영어)
Write a rehash() method for the hash.java program.
It should be called by insert() to move the entire hash table to an array about twice as large whenever the load factor exceeds 0.5.
The new array size should be a prime number. Refer to the section "Expanding the Array" in this chapter.
Don't forget you'll need to handlke items that have been "deleted," that is, written over with -1.
그리고 다음은 hash.java 입니다.
import java.io.*;
////////////////////////////////////////////////////////////////
class DataItem
{ // (could have more data)
private int iData; // data item (key)
//--------------------------------------------------------------
public DataItem(int ii) // constructor
{ iData = ii; }
//--------------------------------------------------------------
public int getKey()
{ return iData; }
//--------------------------------------------------------------
} // end class DataItem
////////////////////////////////////////////////////////////////
class HashTable
{
private DataItem[] hashArray; // array holds hash table
private int arraySize;
private DataItem nonItem; // for deleted items
// -------------------------------------------------------------
public HashTable(int size) // constructor
{
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1); // deleted item key is -1
}
// -------------------------------------------------------------
public void displayTable()
{
System.out.print("Table: ");
for(int j=0; j<arraySize; j++)
{
if(hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
// -------------------------------------------------------------
public int hashFunc(int key)
{
return key % arraySize; // hash function
}
// -------------------------------------------------------------
public void insert(DataItem item) // insert a DataItem
// (assumes table not full)
{
int key = item.getKey(); // extract key
int hashVal = hashFunc(key); // hash the key
// until empty cell or -1,
while(hashArray[hashVal] != null &&
hashArray[hashVal].getKey() != -1)
{
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
}
hashArray[hashVal] = item; // insert item
} // end insert()
// -------------------------------------------------------------
public DataItem delete(int key) // delete a DataItem
{
int hashVal = hashFunc(key); // hash the key
while(hashArray[hashVal] != null) // until empty cell,
{ // found the key?
if(hashArray[hashVal].getKey() == key)
{
DataItem temp = hashArray[hashVal]; // save item
hashArray[hashVal] = nonItem; // delete item
return temp; // return item
}
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
}
return null; // can't find item
} // end delete()
// -------------------------------------------------------------
public DataItem find(int key) // find item with key
{
int hashVal = hashFunc(key); // hash the key
while(hashArray[hashVal] != null) // until empty cell,
{ // found the key?
if(hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // yes, return item
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
}
return null; // can't find item
}
// -------------------------------------------------------------
} // end class HashTable
////////////////////////////////////////////////////////////////
class HashTableApp
{
public static void main(String[] args) throws IOException
{
DataItem aDataItem;
int aKey, size, n, keysPerCell;
// get sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
keysPerCell = 10;
// make table
HashTable theHashTable = new HashTable(size);
for(int j=0; j<n; j++) // insert data
{
aKey = (int)(java.lang.Math.random() *
keysPerCell * size);
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
}
while(true) // interact with user
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, delete, quit or find: ");
char choice = getChar();
switch(choice)
{
case 's':
theHashTable.displayTable();
break;
case 'i':
System.out.print("Enter key value to insert: ");
aKey = getInt();
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
break;
case 'd':
System.out.print("Enter key value to delete: ");
aKey = getInt();
theHashTable.delete(aKey);
break;
case 'f':
System.out.print("Enter key value to find: ");
aKey = getInt();
aDataItem = theHashTable.find(aKey);
if(aDataItem != null)
{
System.out.println("Found " + aKey);
}
else
System.out.println("Could not find " + aKey);
break;
case 'q':
System.out.println("Good bye");
System.exit(0);
default:
System.out.print("Invalid entry\n");
} // end switch
} // end while
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//--------------------------------------------------------------
} // end class HashTableApp
////////////////////////////////////////////////////////////////