해쉬

• 프로그래머스 연습문제

Hash 함수

key,value

: 문자열을 key로 문제를 풀어야 하는 경우 사용한다. - Map, Json

Hash의 속도 O(1)

함수에서 리턴된 값을 가지고 배열에 접근 하기 때문에 속도가 O(1)이 나온다
Hash를 안쓰면 하나씩 모두 찾아야 해서 속도가 Max,Min과 같이 O(N)이 나온다.

코드구현

• 처음 구조 잡기

public class HashFunction2 {
   public int hash(String key) {
       return 0;
   }
}

• 핵심로직 : 입력받은 key를 한 글자씩 ascii code로 바꿔서 더한다.

public class HashFunction2 {
   public int hash(String key) {
       for (int i = 0; i < key.length(); i++) {
 
           asciiSum += key.charAt(i);
           
       }
     
       return asciiSum % 90; // 
   }

HashTable

• Hash → 자체는 특정 값을 리턴하는 함수(메소드)
• HashTable → hash함수를 이용해 array에 접근하는 자료구조
• 값을 넣을때도 hash(key)를 쓰고
  값을 뺄 때도 hash(key)를 쓴다.
  그래서 접근 속도가 O(1)이 나와서 빠른 자료구조

HashTable with size

생성자: public HashTable(int size)

• size 크기는 Hash충돌이 나지 않으면서도 메모리를 너무많이 쓰지 않는 크기로 정한다. (공식은 없음)

public class HashTable {

   private int size = 10000;   // size 변수선언 

   public HashTable() {  // 기본 생성자 주입
   }

   public HashTable(int size) { // 매개변수가 size인 생성자
       this.size = size;
   }

   public int hash(String key) {  // 만들었던 hash 함수 
       int asciiSum = 0;
       for (int i = 0; i < key.length(); i++) {
           asciiSum += key.charAt(i);
       }
       return asciiSum % size; // 나머지로 index를 만드는 이유? 
     
   }
}

• 나머지로 index를 만드는 이유

1. 지정된 크기의 배열에 값을 저장 하기 때문
2. size로 정한 배열의 어딘가로 가도록 하기 위함
   ex) 배열 사이즈가 1000이라면 asciiSum % 1000을 하면 0~999 사이의 값이 나와서 벗어나지 않는다

• main()에 이름 Hashtable 사용

String[] names = new String[]{"name1",
"name2", "name3", "name4"};

HashTable ht = new HashTable();
Set<Integer> nameSet = new HashSet<>();
for (int i = 0; i < names.length; i++) {
   nameSet.add(ht.hash(names[i]));
}
System.out.printf("%s %s", names.length, nameSet.size());

HashTable.insert(key, value)

• key와 value를 받아 insert 하도록 설계
• 생성자, 맴버변수(size, table)

public class HashTable {...}

public void insert(String key, Integer value) {
   int hashCode = hash(key);
   this.table[hashCode] = value;
   System.out.println(key+ " " +hashCode + "방에 저장이 완료 되었습니다.");
}

HashTable.search(key)

• this.table[hash(key)]
  key를 다시 hash로 만들어서 array에서 값을 뽑아온다

public int search(String key) {
   return this.table[hash(key)];
}

해쉬충돌

위 코드까지는 작성은 하지만 틀린 값을 보여주고 있다. (위험한 상태) 그 이유는 해쉬 충돌 때문이다.
같은 hash값이 생성 되었을 때 어떻게 할 것인지? -> 내일