기본 콘텐츠로 건너뛰기

개발 공부 - [해슁] hashing - 3

 좋은 해쉬 함수는

    - 현실에서는 키들이 랜덤하지 않다.
    - 만약 키들의 통계적 분포에 대해 알고 있다면, 이를 이용하여 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어렵다.
    - 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 것이 바람직하다
    -> 예시로 사람 이름이 Z로 시작하는 사람이 적고 A로 시작하는 사람이 많은 것 처럼

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



해쉬함수

Division 기법

h(k) = k mod m (사실 모든 해쉬함수들이 마지막에 하는 일 -> 마지막에 변환하는 일)
ex) m = 20 and k = 91 -> h(k) = 11

장점 : 한번의 mod연산으로 계산, 따라서 빠름
단점 : 어떤 m 값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p 이면 키의 하위 p비트가 해쉬 함수값이 된다.


보통 이 전 단계에서 복잡한 과정을 거쳐서 마지막 과정에 division 기법 적용해서 사용하는데, 이전 단계에서

Multiplication 기법이나 기타등등을 통해서 사용
- 0에서 1 사이의 상수 A를 선택 : 0<A<1 (소수)
- kA의 소수 부분만을 택한다
- 소수 부분에 m을 곱한 후 소수점 아래를 버린다.


Hash code in Java

- java의 Object 클래스는 hashCode() 메서드를 가진다.
따라서 모든 클래스는 hashcode()메소드를 상속받는다.
이 메소드는 하나의 32비트 정수를 반환한다.

x.equals(y)이면 x.hashcode()==y.hashcode()이다.
하지만 역은 성립하지 않는다.

Object 클래스의 hashCode()메소드는 객체의 메모리 주소를 반환하는 것으로 알려져 있다.

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



-> 이거 hashcode() 함수 사용해서 해시값 비교할 때 쓰는 양반임.
=> 이거... 실제로 사용이... Java에서 가능하긴 헌데... 파일을 직접 만질 일이 적어서 별로 신경 안 쓰고 살았던 소중한 함수 ...


hashcode는 임의의 32비트 (음/양수) 정수이고
Hash 함수는 0에서 M-1까지 정수인데
private int hash(key key){
    return (key.hashcode() & 0x7fffffff) % M;    
}



HashMap
4장에서 다룬 TreeMap 클래스랑 비슷한 인터페이스를 제공한다 (Map을 구현)
내부적으로 하나의 배열을 해쉬 테이블로 사용한다.
체이닝으로 충돌을 해결한다
load factor를 (0~1사이 실수)지정 가능하다.
저장된 키의 개수가 load factor 를 초과하면 더 큰 배열을 할당하고 저장된 키들을 재배치한다.


HashSet
이거는 Set 집합임
https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
7부터 지원 가능했었음.

HashSet는 다음과 같은 특징이 있는데,

  • 중복된 값을 허용하지 않습니다.
  • 순서를 보장하지 않습니다.
  • null 값을 저장할 수 있습니다.
  • 내부적으로 HashMap을 사용하여 데이터를 저장합니다.
참고 : https://codechacha.com/ko/java-collections-hashset/

사실 그냥 HashSet Object처럼 선언해서 그냥 set처럼 쓰면 됨

C++은... 사실 안 쓰긴 허는데
unordered_set이라고 hashset 같이 생긴 게 있음

댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야