Hash Table, ArrayList

1. Linked List를 이용한 Hash Table 구현 (Python)

이 경우에서 최악의 경우에는 O(N)이고 최적의 경우는 O(1)이다.

class Node:
    def __init__(self, data, prevnode = None, nextnode = None):
        self.data = data
        self.prevnode = prevnode
        self.nextnode = nextnode

class LinkedList:
    def __init__(self, root = None):
        self.root = root

    def insert(self, data):
        now = self.root

        if self.root == None:
            self.root = Node(data)
        
        else:
            while now.nextnode != None:
                now = now.nextnode

            newNode = Node(data,now)

            now.nextNode = newNode

    def search(self, data):
        now = self.root

        while now != None:
            if now.data == data:
                return now
            else:
                now = now.nextnode

        return None

    def delete(self,data):
        now = self.root

        while now != None:
            if now.data == data:
                if now == self.root:
                    self.root = None
                    return True
                else:
                    now.prevnode.nextnode = now.nextnode
                    return True
            else:
                now = now.nextnode

        return False

class HashTable:
    def __init__(self,n):
        self.arrays = [LinkedList() for _ in range(n)]
        self.n = n

    def insert(self,value):
        hashvalue = hash(value)
        index = hashvalue%self.n
        self.arrays[index].insert(value)

    def search(self,value):
        hashvalue = hash(value)
        index = hashvalue%self.n
        return self.arrays[index].search(value)

    def delete(self,value):
        hashvalue = hash(value)
        index = hashvalue%self.n
        return self.arrays[index].delete(value)

 

* 또 다른 구현법으로는 Balanced Binary Search Tree를 이용하는 방법이다. 이 경우에는 O(logN)이 되고, 미리 배열의 크기를 할당하지 않아도 되기 때문에, 잠재적으로 적은 공간을 사용한다는 장점이 있다.

 

2. ArrayList 구현 (Java)

: 중간에 배열 길이를 두 배 하는 경우가 있지만, 평균적으로 각 insert는 O(1)이 소요된다.

class ArrayList {
    Object[] array = null;
    int capacity = 0;
    int size = 0;

    ArrayList(int capacity){
        this.capacity = capacity;
        array = new Object[capacity];
        this.size = 0;
    }

    boolean doubleArray(){
        try{
            Object[] newArray = new Object[capacity*2];
            this.capacity = this.capacity * 2;
            System.arraycopy(this.array, 0, newArray, 0, this.array.length);
            this.array = newArray;
        }catch(Exception e){
            return false;
        }
        return true;
    }

    boolean insertFront(Object value){
        if(this.size + 1 >= this.capacity){
            boolean result = doubleArray();
            if (result == false){
                return false;
            }
        }

        /*
        for(int i = this.size; i>=0; i--){
            this.array[i] = this.array[i-1];
        }
        */

        System.arraycopy(this.array,0,this.array,1,this.size);

        this.array[0] = value;
        this.size += 1;
        return true;
    }

    boolean insertEnd(Object value){
        if(this.size >= this.capacity){
            boolean result = doubleArray();
            if (result == false){
                return false;
            }
        }

        this.array[this.size] = value;
        this.size += 1;

        return true;
    }

    boolean insert(int index, Object value) {
        if (this.size + 1 >= this.capacity) {
            boolean result = doubleArray();
            if (result == false) {
                return false;
            }
        }

        System.arraycopy(this.array, index, this.array, index + 1, this.size - index);
        this.array[index] = value;
        this.size += 1;
        return true;
    }

    boolean delete(Object value){
        int index = 0;

        for (index = 0; index<=this.size; index++){
            if (this.array[index] == value){
                break;
            }
        }

        if (index > this.size){
            return false;
        }

        System.arraycopy(this.array,index, this.array, index-1, this.size-index);
        this.size -= 1;
        this.array[this.size] = null;
        return true;
    }
}