1 / 10 일 모각코 제 4회 결과

6 주차 : Hashing , 삽입하는 동안 발생하는 총 충돌횟수를 누적하는 메소드 put 을 여러가지 해싱법으로 구현

LinearProbingHashTable 의 put 메소드 

public Object put(Object key, Object value) {

if (used > loadFactor*entries.length) rehash(); 

int h = hash(key);

for (int i = 0; i < entries.length; i++) { 

int j = nextProbe(h,i);

Entry entry = entries[j]; 

if (entry == null) {

entries[j] = new Entry(key, value); 

++size;

++used;

return null; // insertion success

}

if (entry == NIL) { 

count++; // 충돌횟수 증가 

continue;

}

if (entry.key.equals(key)) {

Object oldValue = entry.value;

int v = (int)entry.value;

entries[j].value = ++v; // value 값 증가  

return oldValue; // update success 

}

count++; // 충돌횟수 증가 

}

return null;

}

DoubleHashingHashTable 의 put 메소드 

public Object put(Object key, Object value) {

if (used > loadFactor*entries.length) rehash(); 

int h = hash(key);

int h2 = hash2(key);

for (int i = 0; i < entries.length; i++) { 

int j = nextProbe(h,h2,i);

Entry entry = entries[j]; 

if (entry == null) {

entries[j] = new Entry(key, value); 

++size;

++used;

return null; // insertion success

}

if (entry == NIL) {

count++; // 충돌횟수 증가 

continue;

}

if (entry.key.equals(key)) {

Object oldValue = entry.value;

int v = (int)entry.value;

entries[j].value = ++v; //value 값 증가 

return oldValue; // update success 

}

count++; // 충돌횟수 증가 

}

return null;

}

QuadraticProbingHashTable 의 put 메소드 

public Object put(Object key, Object value) {

if (used > loadFactor*entries.length) rehash(); 

int h = hash(key);

for (int i = 0; i < entries.length; i++) { 

int j = nextProbe(h,i);

Entry entry = entries[j]; 

if (entry == null) {

entries[j] = new Entry(key, value); ++size;

++used;

return null; // insertion success

}

if (entry == NIL) { 

count++; // 충돌횟수 증가 

continue;

}

if (entry.key.equals(key)) {

Object oldValue = entry.value;

int v = (int)entry.value;

entries[j].value = ++v; // value 값 증가 

return oldValue; // update success 

}

count++; // 충돌횟수 증가 

}

return null;

}

SeparateChainingHashTable 의 put 메소드 

public Object put(Object key, Object value) {

int h = hash(key);

for (Entry e = entries[h]; e != null; e = e.next) {

if (e.key.equals(key)) {

Object oldValue = e.value;

int v = (int)e.value;

e.value = ++v; // value 값 증가 

return oldValue; // successful update

}

}

entries[h] = new Entry(key,value,entries[h]); 

++size;

if (size > loadFactor*entries.length) rehash(); 

return null; // successful insertion

}