자료구조 및 알고리즘

해시

해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다.

해시값을 인덱스화 해서 데이터에 저장
데이터가 저장되는 공간을 Bucket이라고 함
해시는 데이터를 빠르게 저장하고 빠르게 가져오는 기법 중 하나
키에 특정 연산을 적용하여 테이블의 주소를 계산한다.
키는 중복될 수 없다. 데이터는 키에 따라 관리됨
데이터 간에 순서가 존재하지 않는다.

해시함수 : 임의의 데이터(키)를 특정값(해시값)으로 매핑시키는 함수

public int hashCode(){
    int h = this.hash;
    if(h == 0 && this.value.length > 0){
        this.hash = h = this.isLatin1() ? StringLatin1.hashCode(this.value) : StringUTF16.hashCode(this.value);
    }
    return h;
}

String의 hashcode

결과를 보면 "Hello"의 해쉬값은 첫번째와 세번째 동일한 값이 나온다. -> 키가 고유하다는 뜻

좋은 해시 함수는 어떤 함수일까?

• 키 값을 고르게 분포시킴
• 빠른 계산
• 충돌(해시충돌) 최소화 ➡️ 키값이 다른데 결과값이 같은경우를 말함

https://bit.ly/3FVdhDa
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.