HashMap -chaning 기법

Hash 자료구조란 ?

Hash는 key의 값으로 value 값을 찾아내는 자료구조이다.

Hashtable은 값을 저장할 장소를 뜻하며,

각 값의 주소는 key 값을 해쉬화를 통해, 주소를 반환한다.

하지만 이러한 방법으로는 주소가 겹칠수도있기 때문에,

chaning 기법을 쓴다.

Hash + LinkedList라고 생각하면 쉽다.

동일한 주소값에  next 객체를 생성하여, 연속된 LinkedList를 생성하면된다.

 

 

 

public class MyHash {

    private Slot[] HashTable;

    public MyHash(Integer size) {
        this.HashTable = new Slot[size];
    }

    public class Slot {
        String key;
        String value;
        Slot next;

        public Slot(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    public int hashFunc(String key) {
        return (int) key.charAt(0) % this.HashTable.length;
    }

    public boolean saveData(String key, String value) {

        Integer address = hashFunc(key);
        if (this.HashTable[address] != null) {
            if (this.HashTable[address].key == key) {
                this.HashTable[address].value = value;
            } else {
                Slot prevSlot = this.HashTable[address];
                Slot findSlot = this.HashTable[address];
                while (findSlot != null) {
                    prevSlot = findSlot;
                    findSlot = findSlot.next;
                }
                prevSlot.next = new Slot(key, value);
            }
        } else {
            this.HashTable[address] = new Slot(key, value);
        }
        return true;

    }

    public String getData(String key) {
        Integer address = hashFunc(key);

        if (this.HashTable[address] != null) {
            Slot slot = this.HashTable[address];
            while (slot != null) {
                if (slot.key == key) {
                    return slot.value;
                }
                slot = slot.next;
            }
            return null;
        }
        return null;
    }