[%] 해시맵 이렇게 구현하는 경우도 있음?

[익명(59.14)]

트리로 만들어서

예를들어서 fcha3xc231이다 하면

f-c-h-a-... 이런식으로 트리 만들어서 저장하면 저장공간 획기적으로 줄일 수 있을 것 같은데

[전붕이1(crmerry0409)]

그럼 루트 밑에 a~z까지 알파벳 숫자에 각종 문자까지 child가 수십 개 나오지않나

[익명(39.7)]

입력 들어올때만 생성하면.. 안되나?

[전붕이1(crmerry0409)]

그리고 해시맵이면 search가 O(1)이어야 하는데, 니처럼하면, 해시맵은 당연히 아니고, 그냥 정렬된 트리 정도인데

[익명(39.7)]

Big-O notation에서 n은 데이터 크기에 따라 결정되는데.. 저 경우는 10자리 해시다 하면 무조건 10단계 안에 찾으니까 O(1) 아님?

[전붕이1(crmerry0409)]

차일드가 몇 개일줄 알고 10번만에 찾음? a-z 일 경우 글자 하나찾을 때 최악의 경우 5번 걸리는데

[익명(39.7)]

노드 하나당 a-z0-9 다 넣으면 되지

[전붕이1(crmerry0409)]

그리고 10자리 해시를 10단계안에 찾으면 O(n)임. n이 늘어갈 수록, 필요한 단계도 선형적으로 증가하니까. O(1)은 n이 아무리 늘어도 필요한 계산이 선형적으로 증가하지 않고 거의 동일함

[전붕이1(crmerry0409)]

그럼 노드 하나가 갖는 child가 0~9, a~z.. 노드 하나가 차일드 36개를 갖는 다는 말? 그러면 메모리가 어케줄음

[익명(39.7)]

데이터 자체는 수십수억개를 써도 결국 뱉어내는건 10자리 해시니까 O(1) 아님? 해시가 데이터 비례해서 늘어나는거도 아니고

[익명(39.7)]

그럼 극단적으로 숫자가 작을때 기존 해시맵보다 메모리 이득이 있나

[전붕이1(crmerry0409)]

ㅇㅎ 니말은 결과로 나온 해시를 통으로 저장 안한다는거구만

[익명(39.7)]

미리 생성하는게 아니고 데이터 들어올때만 유동적으로

[전붕이1(crmerry0409)]

저장 공간이야 줄것 같은데, 속도 때문에 안쓸듯. 무조건 10단계 거쳐야하는데

[익명(39.7)]

결국 트레이드오프네

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[전붕이1(crmerry0409)]

비슷할걸

[전붕이1(crmerry0409)]

결국 has의 공통된 preifx를 같이 쓰자! 라는거니까

[전붕이1(crmerry0409)]

a-b-c-d a-b-c-f 해시가 이렇게 나오면, a-b-c까진 공유하고 d, f만 갈라지는 거니까

[익명(59.13)]

트라이아님?

[익명(147.46)]

suffix tree잖아

[익명(118.235)]

해시는 정수값인데 뭔소리

[익명(121.142)]

패트리샤 트리