[자료구조] judy array

#자료구조/알고리즘

Judy array는 연관 배열의 일종이다. 해시테이블보다 빠르고, 메모리도 적게 먹는데다, 캐시 최적화도 잘 되게 설계되어있다고 한다.

근데 가장 큰 문제는 로직과 그 구현이 너무 복잡하다는 것이다. 위키피디아에 따르면 보통 코드가 수천줄이라고 한다.

사실 Judy Array는, Trie에 기반을 두는 구조다. 이름은 배열인데 배열이 아니라 트리의 일종이었다.

하지만, 거의 모든 접근과 수정이 바로 이어지는 Trie답게 트리 밸런싱 같은 비용이 들지 않는다.

이외에도 뭐 캐시라인 fill을 방지해서 캐싱 최적화를 하고, 메모리 효율성도 되게 높다고 하는데... 잘 모르겠다.
나중에 더 공부해서 정리해보겠다.

창시자는 Douglas Baskins와 그의 여동생 Judy라고 한다.