해싱3

해슁3

좋은 해쉬 함수란?

-현실에서는 키들이 랜덤하지 않음

-만약 키들의 통계적 분포에 대해 알고있다면 이를 이용해서 해쉬함수를 고안하는 것이 가능하겠지만 현실적으로

 어려움

-키들이 어떤 특정한 패턴을 가지더라도 해쉬함수값이 불규칙적이되도록 하는게 바람직

 (랜덤보다는 특정 패턴을 가지는게 흔함)

   -해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야한다.

   

  DIVISION 기법

 - h(k) = k mod m

  -예 : m = 20 and k =91 => h(k) =11

  -장점 : 한번의 mod 연산으로 계산. 따라서 빠름

  -단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음.

 

   Multiplication 기법

  -0에서 1사이의 상수 A를 선택 0<A<1 

  -KA의 소수부분만을 택한다.

  -소수 부분에 m을 곱한 후 소수점 아래를 버림

 

Hashing in Java

Java의 Object 클래스는 hashCode() 메서드를 가짐

따라서 모든 클래스는 hashCode() 메서드를 상속받음

이 메서드는 하나의 32비트(음수일수도있다) 정수를 반환한다.

-만약 x.equlas(y)이면 x.hashCode()==y.hashCode()이다.

 하지만 역은 성립하지 않는다.

-Object 클래스의 hashcode() 메서드는 객체의 메모리 주소를 반환하는 것으로 알려짐

-필요에 따라 각 클래스마다 이 메서드를 override 하여 사용한다.

  예) integer 클래스는 정수값을 hashCode로 사용

 

해쉬 함수의 예 : hashCode() for String in java

public final class String 
{
  private final char[] s;
   ...
   public int hashCode()
   {
     int hash =0;
     for( int i=0; i< length(); i++)
      hash=s[i]+(31*hash)
      return hash;
      }
}

 

 

  사용자 정의 클래스의 예

public class Recode
{
  private String name;
  private int id;
  private double value;
  
  ...
  public int hashCode() {
    int hash =17;
    hash =31*hash + name.hashCode();
    hash =31*hash + Integer.valueOf(id).hashCode(); 각각의 datamember들의 해쉬코드,,,
    hash =31*hash + Double.valueOf(value).hashCode();
    return hash;
    }

 모든 멤버들을 사용하여 hashCode를 생성한다.

hash code는 음수일수도 있다. 테이블이 정해지지않은 상태에서 임의의 32비트정수값을 리턴해주는 메서드

이것을 다시 내가 원하는 테이블 사이즈 배열 인덱스로 한번 더 변환해야.. Hash함수로 사용가능

 

HashMap in java

-내부적으로 하나의 배열을 해쉬 테이블로사용

-chaining으로 충돌 해결

-load factor를 지정할수있음(0~1 사이의 실수)

-저장된 키의 개수가 load factor를 초과하면 더 큰 배열을 할당하고 저장된 키들을 재배치(re-hashing)

 

HashSet // set(집합) data type을 구현하는 클래스

HashSet(MyKey> set = new HashSet<Mykey>();
set.add(MyKey);
if(set.contain(thekey)) //특정원소 있는지 없는지 체크

int k = set.size();
set.remove(thekey);
...

 

참조

www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4103?tab=note