Hash, 해쉬코드,해쉬함수는 뭘까?

Hash란 무엇일까요?? 아무래도 프로그래밍을 하다보면 자주 듣게 되는 단어인거 같은데

저는 잘 모르겠었거든요…. 그래서 한번 정리도 하고, 이해도 할겸 글을 써볼려고합니다!

일단 Hash라고 하면은 데이터를 처리하는 기법중 하나인데, 주로 저장,검색과 같은 기능을 구현할때 좋은 성능을

보여준다고하여 많은 쓰임새를 얻고 있습니다!

 

 

Hash를 쓸때 중점적으로 알아봐야 할건?

바로 key, value 입니다!

key와 value는 한쌍으로 존재를 하는데요 이것을 바로 Hash Table 이라고 부릅니다.

 

---

Key는 Hash에서 매핑을 할 때 사용하는 인덱스.

라고 생각하면 전체적인 이해는 되는거 같습니다!! 그리고 Key는 절대로 중복이 되지 않습니다.

만약에 같은 Key에 또 다른 데이터를 넣게 되면 전에 있던 데이터는 삭제되고 새로 들어온 데이터가 Key와 쌍을 이루게 됩니다.

---

 

Value는 Key로 매핑했을때 나오는 결과값입니다.

Hash는 배열이 가지고 있는 인덱스와 다르게 순차적으로 저장이 되는게 아닌 전역에 골고루 분포 되있다고 설명합니다.

따라서, 배열 보다는 빠르게 값을 찾을 수 있다는 장점이 존재하게 되죠.

---

Hash 코드, Hash 함수??

 

Hash코드 :

Hash를 이용하여 값을 생성하면 고유의 주소 값이 생기는데 이것을 숫자로 변환한 것을 Hash코드 라고 부릅니다.

그렇다면 자바에서는 ???

Heap 영역에 생성된 인스턴스에 대한 참조 값이 해시코드라고 생각할수 있다는겁니다.

 

 

Hash 함수:

데이터의 효율적인 관리를 위해 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터를 매핑해주는 함수입니다.

쉽게 말해서!… 암호화 과정?? 이라고 생각해도 되죠???

💡 비밀번호를 입력해서 저장할때 해쉬함수를 이용하여 변환을 시키면 관리자도 비밀번호 내용을 보는게 아닌 해쉬화가 된 값을 보게됩니다

---

Hash Collision (해시 충돌)

만약에 같은 key값에 다른 value가 들어오게 된다면??

기존에 있던 value는 사라지고 새로운 value가 들어온다고 했죠??

이게 바로 “해시충돌”의 케이스 입니다.

그렇다면 어떻게 해결해야 할까요?

Chaining : 해시 충돌이 일어나면 연결된 리스트를 사용해 데이터를 연결.

체이닝은 추가적인 메모리를 이용해 동일한 주소지에 연결리스트로 하나씩 순차적으로 저장하는것을 의미합니다.

체이닝은 연결리스트만 사용하면 되서 복잡하지 않고 같은 주소값을 그대로 사용할 수 있다는 장점이 있지만,

특정 주소에 만약에 값이 계속 쌓이게 되면 성능이 현저하게 낮아지고 많은 메모리 공간을 잡아먹습니다

(해시테이블을 사용하는 이유는 ⇒ 키값을 통해 바로 값을 찾고자 하는건데, 이렇게 연결된 리스트를 사용하여 저장하면

키값을 통해 value가 담긴 버켓에 들어와서 또 다시 값을 찾아야 한다는겁니다. 그렇다면 속도가 느려지겠죠?)

.

Open Addressing : 해시충돌이 일어나면 다른 주소지에 삽입하는 방식

개방주소법이라고 불리는데요. 체이닝과 다르게 추가적인 메모리를 필요로 하지 않는 장점이 있습니다.

크게 3가지 정도의 방법이 있습니다:

1. Linear Probing : 해시 충돌 발생시 바로 옆 주소지나 몇개의 주소지를 뛰어 넘어 데이터를 삽입합니다.
2. Quadratic Probing : 해시 충돌시 제곱만큼 건너 뛰어 데이터를 삽입합니다.
3. Double Hashing : 해시 충돌시 다른 해시함수를 한번 더 적용시킵니다.

---

자 그렇다면 해시라는 개념은 왜 생겼을까요?

바로 LinkedList처럼 추가와 삭제시 시간이 걸리는 단점과, 선형검색을 해야하는 비효율성을 해결하고자 나온 방법입니다.

ArrayList처럼 index로 해당 데이터를 바로 찾아가능 기능이 구현되어 있는 거처럼.

LinkedList에서 해시를 도입하면 Key의 중복만을 검사하고 추가삭제를 할때 빠르게 변경해준다는거죠.

음…여기까지 이해한거 같은데 다음번엔 실제적인 코드를 가지고 구현을 해보겠습니다

휴 인생….