해쉬 함수 구현 (hash function implementation) 링크 정리

이것도 한 3-4년전에 정리했다가 가끔 업데이트 한 것 같은데… 나름 괜찮은 링크가 몇 개 있어 공유한다. 이것도 앞으로는 이 페이지에서 업데이트를 하겠다. 오래 지나다보니 인터넷에 있는 정보라도 링크가 깨진 것들이 많아 지웠는데 아쉽다. 다행히 이 페이지는 web archive에서 찾을 수 있어 다행이다 싶다.

General

• Which hashing algorithm is best for uniqueness and speed?
• Can one construct a “good” hash function using CRC32C as a base?
  • CRC32가 hash table등을 위한 목적으로 좋은가? (키가 uniform distribution으로 나오는가?)
• State of the hash functions, 2012
• Hash Function
  • 해쉬 함수 총정리 (강력 추천)

SW-based Implementations

• http://www.cse.yorku.ca/~oz/hash.html
  • 단순한 해쉬 함수들 구현 소개 (바로 쓸 수 있는 코드들)
• Implementing SSE 4.2’s CRC32C in software
  • SW 기반 HW 기반 코드 소개
• Benchmarking CRC32 and PopCnt instructions
• The Hash – 각종 hash 함수 소개 및 성능 평가
• MurmurHash – 최근 가장 빠른 성능의 해쉬함수 중 하나로 평가되고 있는 Murmur의 원구현 소스 (코드 읽기 쉬워 포팅 쉬움)
• xxHash – 현재 가장 빠르다고 주장되고 있는 해쉬 함수 구현

HW-based Implementations

• _mm_crc32_u64 poorly defined
  • SSE4.2 제공 crc32 hashing 용례
• SSE4.2 and the new CRC32 instruction
• http://home.ustc.edu.cn/~shengjie/REFERENCE/sse4_instruction_set.pdf
  • SSE4 instruction set reference
• Fast, Parallelized CRC Computation Using the Nehalem CRC32 Instruction
• Intel® SHA Extensions