원형큐 / 해시테이블 의사코드 정리

순환 대기열을 위해서는 적어도 두 개의 멤버 변수들이 필요하다. 하나는 대기열의 시작을 가리키는 색인이고,

또 하나는 대기열 안에 들어 있는 항목들의 개수 이다.

int m_front //시작가리키는 색인

int m_count //대기열 안에 들어있는 항목들의 개수

인큐함수

최초의 빈 색인을 찾고 거기에 새 항목을 넣기만 하면된다. 최초의 빈 색인은 다음 공식으로 구할 수 있다.

index = m_first + m_count;

그러냐 이 공식은 index가 배열의 끝을 넘어갈 수가 있다. 만약에 0 ~ 7인덱스를 가지고 있는 크기의 큐라면

567을 추가하고 8을 추가하게 될때 m_first + mcount = index가 8이 되므로. (0 + 8) 유효한 색인이 아니다 그래서

8을 다시 0인덱스로 해야한다 그래서 나머지 연산자가 필요한것임..

(m_first + m_count) % m_size(이 사이즈는 크기 - 1이 된다 인덱스 때문에..) 이렇게 하면 항상 0 ~ 7범위의 인덱스가 나오게 된다.

그리고 인큐가 되면 m_count ++를 올리게 된다.

디큐함수

이건 간단함. 대기열이 비어있지 않으면 시작 색인을 1증가시키면 된다. 배열의 끝을 넘게 된다면 다시 0으로 설정한다.

front함수

가장 간단하다 m_front가 가리키는 항목을 반환하면 된다.

---

연결 리스트를 사용하는 chaining 해쉬 테이블은 연결 리스트의 단점도 그래도 물려받아, 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 되고 traverse의 캐쉬 효율도 좋지 않다. 대체 자료구조로서 최악의 경우에 O(n)이 아닌 O(log n)의 검색 복잡도를 보장하는 self-balancing tree를 고려해 볼 필요도 있다. 

그러나 해쉬 테이블이 꽉 찰 정도로 운영되거나 상당히 높은 확률로 충돌이 발생하지 않는다면(저렇게 되지 않도록 하는 것이 가장 좋다), 통상적으로 리스트의 길이는 대부분 상당히 짧으며 모든 버켓이 2개 이상의 개체를 가지지도 않기 때문에 연결 리스트를 이용한 chained 해쉬 테이블로도 충분히 효과적이다

그리고 데이터의 크기가 작을 때는 space 오버헤드를 줄이고 캐쉬 효율을 높이기 위해 연결 리스트 대신 dynamic array를 쓸 수도 있다

http://egloos.zum.com/sweeper/v/925740

유명한 해쉬함수의 종류

https://seed.kisa.or.kr/iwt/ko/intro/EgovHashFunction.do

문자열 해싱방법(단순)

unsigned long int stringHash(const char* p_string)

{
    unsigned long int hash = 0;

int i;

int length = strlen(p_string);

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

hash += ((i * 1) * p_string[i]);

}

return hash;

}

각 문자열의 자리 인덱스를 이용해서 값을 계산 누적 활용하는것.

해시 테이블에 자료를 넣을때는 자료와 그에 대한 키를 함께 넣어야 한다.

해시 테이블에서 어떤 자료를 찾을 경우에는 자료의 키로 해시 테이블을 검색하고 그 키가 있는 곳의 자료를 얻는다.

해시 테이블이 왜 소수여야 하는가?

http://asfirstalways.tistory.com/332

그래서 해시 테이블의 기본 자료클래스를 만들때 키값과 데이터를 포함해서 만든다.

class hashEntry

{

public:

int m_key;

int data;

};

public class Hash {
    
    // 데이터를 저장할 Entry는 값과 다음 Entry를 가진다.
    private class Entry{
        private int value;
        public Entry next;
    }
    
    private int size;
    private Entry[] hTable;
    
    // Hash Table은 size와 배열 테이블을 생성한다.
    public Hash(int size){
        
        this.size = size;
        this.hTable = new Entry[size];
    }
    
    // key 값으로 HashTable에 저장될 index를 반환한다.
    public int hashMethod(int key){
        return key % size;
    }
    
    // 저장할 데이터로 key를 추출한다.
    // 실제 Hash 에는 특별한 알고리즘이 적용되 hashCode를 얻는다.
    public int getKey(int data){
        return data;
    }
    
    // data를 HashTable에 저장한다.
    public int add(int data){
        
        // data의 hashCode를 key와 저장할 index를 얻는다.
        int key = getKey(data);
        int hashValue = hashMethod(key);
        
        // 저장할 Entry 생성
        Entry entry = new Entry();
        entry.value = data;
        
        
        // HashTable의 저장할 index가 비어있다면,  저장하고 끝낸다.
        if(hTable[hashValue] == null){
            
            hTable[hashValue] = entry;
            return 0;
        }
        
        
        Entry pre = null;
        Entry cur = hTable[hashValue];
        
        // 해당 index의 연결리스트는 값의 크기가 작은 값부터 큰 순서로 정렬되어있다.
        while(true){
            
            if(cur == null){     // Hash Table에 저장할 index가 비어있으면 
                
                hTable[hashValue] =entry;  // 해당 index에 저장
                return 0;
            
            }else if(cur.value < key){    // 해당 index의 커서 노드의 값이 key보다 작으면
                
                // 커서를 하나 뒤로 옮긴다.
                pre = cur;            
                cur = cur.next;
            
            }else{     // 해당 index의 커서 노드의 값이 key 보다 크다.(여기에 저장)
                
                // 커서 노드가 HashTable의 첫번째 노드이면
                if(cur == hTable[hashValue]){
                    
                    // 삽입 노드를 첫번째 노드로 삽입하고 다음 노드를 커서노드로 지정한다.
                    entry.next = cur;
                    hTable[hashValue]= entry;
                    return 0;
                    
                }else{    // 첫번째 노드가 아니면
        
                    // 삽입 노드의 다음 노드로 커서노드를 지정하고
                    // 전 노드의 다음 노드를 삽입노드로 지정한다.
                    entry.next = cur;
                    pre.next = entry;
                    return 0;
                }
            }
        }
    }
    
    
    // data가 있는 위치를 얻는다.
    public int get(int data){
        
        int key = getKey(data);
        int hashValue = hashMethod(key);
        
        // data가 있는 index의 첫번째 노드를 얻는다.
        Entry cur = hTable[hashValue];
        
        while(true){
            
            if(cur == null){    // index 가 비어있다면 -1 반환
            
                return -1;
            
            }else if(cur.value == key){    // 커서의 값과 키가 같으면 0 반환
                
                return hashValue;
            
            }else if(cur.value > key){    // 커서의 값이 키보다 크면 -1 반환
                                                    // 리스트는 작은 값에서 큰 값으로 정렬되어있다.
                return -1;
            
            }else{        // 커서의 값이 키보다 작으면 다음 노드로 커서 이동
                
                cur = cur.next;
            }
        
        }
    }
    
    // data가 있는 노드를 반환한다.
    private Entry getEntry(int data){
        
        int key = getKey(data);
        int hashValue = hashMethod(key);
        
        // HashTable의 index의  첫번째 노드와 두번째 노드
        Entry pre = hTable[hashValue];
        Entry cur = pre.next;
        
        while(true){
            
            if(cur == null){    // 커서 노드가 null 이면 null 반환
                
                return null;
            
            }else if(cur.value == key){    // 커서 노드의 값이 키와 같으면 전 노드를 반환
                
                return pre;
                
            }else if(cur.value > key){    // 커서의 값이 키보다 크면 null 반환
                
                return null;
            
            }else{            // 커서의 값이 키보다 작으면 커서를 다음으로 이동
                
                pre = cur;
                cur = cur.next;
            }
        }
    }
    
    // data 를 제거
    public int remove(int data){
        
        Entry pre = null;
        
        // data가 있는 노드의 전노드를 가져오고 null이면 -1 반환
        if((pre=getEntry(data))== null){
            return -1;
        }
        
        // 전 노드가 data의 다음노드를 가리키게 한다.
        // data 노드를 건너뛰게 연결한다 (제거)
        Entry cur = pre.next;
        pre.next = cur.next;
        return 0;
    }
    
    public String toString(){
        
        StringBuffer result = new StringBuffer();
        Entry cur = null;
        
        for(int i=0; i<size; i++){
            
            result.append("[" + i + "]\t");
            cur = hTable[i];
            
            if(cur == null){
                result.append("n ");
                
            }else{
                
                while(cur!=null){
                    result.append(cur.value + "");
                    cur = cur.next;
                }
            }
            result.append("\n");
        }
        
        return result.toString();
    }

}

여기서 리스트에 넣을때 자료의 크기로 비교하는 부분을 그냥 다음 리스트에 연결하는걸로 바꾸면 더 간단하다.