수다닷컴

제가 보고있는 책에서
해쉬 2차 탐색법 (quadratic probing ) 에 관련된 문제풀다가 질문이 생겼어요
총 세가지 질문이 있습니다...

현재 해쉬 공부 중인데요

첫번째 질문으로는,,
제가 보고 있는 자료구조 책에서
해쉬 2차탐색법 (quadratic probing)은
isempty() 메소드에서는 단순히 현재 차지되어 있는 slot 싸이즈를 0으로 설정하는,, 즉

public boolean isempty()
{
return currentsize== 0;
}

이라고 쓸수 없다고 하는데요.. 그럼 어떻게 써야하나요?..
이해가 안가는걸요..

길어서 읽기 힘드시겠지만..
현재 다음과 같은 소스를 기반으로 문제를 풀고 있어서요..
이게있어야 제 질문이 이해가 가실거예요

// quadraticprobing hash table class
//
// construction: an approximate initial size or default of 101
//
// ******************public operations*********************
// bool insert( x ) -- insert x
// bool remove( x ) -- remove x
// bool contains( x ) -- return true if x is present
// void makeempty( ) -- remove all items
//boolean isempty( ) -- return true if hash table is empty
// anytype find( anytype x ) -- return reference to x, if present; null otherwise
// object[] toarray() -- return array of active items in hash table

빨간 부분이 제가 질문 드리려는 메소드들이예요
이 소스안에는 없고요.. 제가 쓴게 맞는지 확인하고싶어요

public class quadraticprobinghashtableanytype
{
private static final int default_table_size = 101;
private hashentryanytype [ ] array; // the array of elements
private int currentsize; // the number of occupied cells

public quadraticprobinghashtable( )
{
this( default_table_size );
}
public quadraticprobinghashtable( int size )
{
allocatearray( size );
makeempty( );
}

private void rehash( )
{
hashentryanytype [ ] oldarray = array;
allocatearray( nextprime( 2 * oldarray.length ) );
currentsize = 0;

for( int i = 0; i oldarray.length; i++ )
if( oldarray[ i ] != null && oldarray[ i ].isactive )
insert( oldarray[ i ].element );
}

public void remove( anytype x )
{
int currentpos = findpos( x );
if( isactive( currentpos ) ) {
array[ currentpos ].isactive = false;
}
}

public boolean contains( anytype x )
{
int currentpos = findpos( x );
return isactive( currentpos );
}

private boolean isactive( int currentpos )
{
return array[ currentpos ] != null && array[ currentpos ].isactive;
}

public void makeempty( )
{
currentsize = 0;
for( int i = 0; i array.length; i++ )
array[ i ] = null;
}

private int myhash( anytype x )
{
int hashval = x.hashcode( );
hashval %= array.length;
if( hashval 0 )
hashval += array.length;
return hashval;
}

private static class hashentryanytype
{
public anytype element; // the element
public boolean isactive; // false if marked deleted
public hashentry( anytype e )
{
this( e, true );
}
public hashentry( anytype e, boolean i )
{
element = e;
isactive = i;
}
}

private void allocatearray( int arraysize )
{
array = new hashentry[ arraysize ];
}

private static int nextprime( int n )
{
if( n % 2 == 0 )
n++;
for( ; !isprime( n ); n += 2 )
;
return n;
&nbsbsp; }

private static boolean isprime( int n )
{
if( n == 2 || n == 3 )
return true;
if( n == 1 || n % 2 == 0 )
return false;
for( int i = 3; i * i = n; i += 2 )
if( n % i == 0 )
return false;
return true;
}

private int findpos( anytype x )
{
int offset = 1;
int currentpos = myhash( x );

while( array[ currentpos ] != null &&
!array[ currentpos ].element.equals( x ) )
{
currentpos += offset; // compute ith probe
offset += 2;
if( currentpos = array.length )
currentpos -= array.length;
}

return currentpos;
}

public void insert( anytype x )
{
// insert x as active
int currentpos = findpos( x );
if( isactive( currentpos ) )
return;
array[ currentpos ] = new hashentryanytype( x, true );
// rehash; see section 5.5
if( ++currentsize array.length / 2 )
rehash( );
}그리고 또 다음 두개 문제들도 위의 소스 기반인 문제인데요
책에 답이 제공이 안되서요.. 제가 맞게 한건지..확인해 주셨으면 해요

첫번째 문제는 해쉬테이블 내용을 배열로 바꾸는거예요 2차탐색법 기준으로요..
implement method public object[] toarray(), which returns an array of the elements stored in the hash table.
if there are 3 active elements stored in the table, the length of the returned array should be 3.제가 쓴건..
public object[] toarray() {
object any [] = new object[this.currentsize];

int i = 0;
for(int j = 0; j array.length ; j++){
if( array[i] != null && array[i].element != null ){
any[i] = array[i].element;
i++;
}
}
return any;
}

이거 맞나요?... 그리고 두번째 문제는 해쉬테이블에서 아이템 찾으면 반환하는.. 문제예요
implement method public anytype find(anytype x), which returns a reference to element x if x is stored in the hash table, and returns null otherwise.

제가 풀기로는...
public anytype find(anytype x)
{
int currentpos = findpos(x);
if( array[ currentpos ] == null || !array[ currentpos ].isactive )
return null;
else
return array[currentpos].element;
}

맞는지.. 확인하고 싶어요..

답변 부탁드려요 감사합니다..

신청하기