이진 트리 vs. 연결 목록 vs. 해시 테이블

이진 트리 vs. 연결 목록 vs. 해시 테이블

---

작업중인 프로젝트의 기호 테이블을 만들고 있습니다. 기호 테이블을 저장하고 생성하는 데 사용할 수있는 다양한 방법의 장단점에 대한 사람들의 의견이 궁금했습니다.

나는 꽤 많은 검색을 해왔고 가장 일반적으로 권장되는 것은 이진 트리 또는 연결 목록 또는 해시 테이블입니다. 위의 모든 장점과 단점은 무엇입니까? (C ++에서 작동)

---

사용 사례는 아마도 "데이터를 한 번 삽입 (예 : 애플리케이션 시작) 한 다음 많은 읽기를 수행하지만 추가 삽입이있는 경우에는 거의 수행하지 않음"일 것입니다.

따라서 필요한 정보를 찾는 데 빠른 알고리즘을 사용해야합니다.

따라서 HashTable이 사용하기에 가장 적합한 알고리즘이라고 생각합니다. 단순히 키 개체의 해시를 생성하고이를 사용하여 대상 데이터에 액세스하는 것이므로 O (1)입니다. 나머지는 O (N) (크기 N의 연결된 목록-한 번에 하나씩 목록을 반복해야하며 평균 N / 2 회) 및 O (log N) (이진 트리-검색 공간을 절반으로 줄입니다. 각 반복-트리가 균형을 이루는 경우에만 구현에 따라 다르므로 균형이 맞지 않은 트리는 성능이 크게 저하 될 수 있습니다.

HashTable에 데이터를위한 충분한 공간 (버킷)이 있는지 확인하십시오 (Re,이 게시물에 대한 Soraz의 의견). 대부분의 프레임 워크 구현 (Java, .NET 등)은 구현에 대해 걱정할 필요가없는 품질입니다.

대학에서 데이터 구조 및 알고리즘에 대한 과정을 수강 했습니까?

---

이러한 데이터 구조 간의 표준 상충 관계가 적용됩니다.

• 이진 트리
  • 구현하기 복잡함 (라이브러리에서 가져올 수 없다고 가정)
  • 삽입은 O (logN)입니다.
  • 조회는 O (logN)입니다.
• 연결된 목록 (정렬되지 않음)
  • 구현의 복잡성이 낮음
  • 인서트는 O (1)
  • 조회는 O (N)입니다.
• 해시 테이블
  • 구현이 매우 복잡함
  • 인서트는 평균 O (1)입니다.
  • 조회는 평균 O (1)입니다.

---

모두가 잊는 것처럼 보이는 것은 테이블에있는 작은 N, IE 몇 가지 기호의 경우 연결 목록이 해시 테이블보다 훨씬 빠를 수 있지만 이론적으로는 점근 적 복잡성이 실제로 더 높다는 것입니다.

Pike의 C 프로그래밍 노트에서 유명한 qoute가 있습니다. "규칙 3. 멋진 알고리즘은 n이 작을 때 느리고 n은 일반적으로 작습니다. 멋진 알고리즘에는 큰 상수가 있습니다. n이 자주 커질 것이라는 것을 알기 전까지는, 화려하지 마세요. " http://www.lysator.liu.se/c/pikestyle.html

나는 당신이 작은 N을 다룰 것인지 아닌지를 당신의 게시물에서 말할 수 없지만 항상 큰 N에 대한 최상의 알고리즘이 반드시 작은 N에 좋은 것은 아니라는 것을 기억하십시오.

---

다음이 모두 사실 일 수 있습니다.

• 키는 문자열입니다.
• 삽입은 한 번 수행됩니다.
• 조회는 자주 수행됩니다.
• 키-값 쌍의 수가 상대적으로 적습니다 (예 : K 정도 이하).

그렇다면 이러한 다른 구조에 대해 정렬 된 목록을 고려할 수 있습니다. 정렬 된 목록은 삽입시 O (N)이고 연결 목록 또는 해시 테이블의 경우 O (1)이고 O (log ₂ )이므로 삽입하는 동안 다른 것보다 성능이 떨어집니다.N) 균형 이진 트리의 경우. 그러나 정렬 된 목록의 조회는 이러한 다른 구조보다 빠를 수 있으므로 (곧 설명하겠습니다) 맨 위에 올 수 있습니다. 또한 모든 삽입을 한 번에 수행하는 경우 (또는 모든 삽입이 완료 될 때까지 조회가 필요하지 않은 경우) O (1)에 대한 삽입을 단순화하고 끝에서 훨씬 빠르게 정렬 할 수 있습니다. 또한 정렬 된 목록은 이러한 다른 구조보다 적은 메모리를 사용하지만 이것이 중요한 유일한 방법은 작은 목록이 많은 경우입니다. 하나 또는 몇 개의 큰 목록이있는 경우 해시 테이블이 정렬 된 목록보다 성능이 뛰어납니다.

정렬 된 목록으로 조회가 더 빠른 이유는 무엇입니까? 글쎄요, 후자의 O (N) 조회 시간과 함께 연결된 목록보다 빠르다는 것이 분명합니다. 이진 트리를 사용 하면 트리가 완벽하게 균형을 유지하는 경우 에만 조회가 O (log ₂ N)로 유지됩니다. 트리의 균형을 유지 (예 : 빨강-검정)하면 복잡성과 삽입 시간이 늘어납니다. 또한 연결 목록과 이진 트리 모두에서 각 요소는 개별적으로 할당 된 ¹ 노드 입니다. 즉, 포인터를 역 참조해야하고 잠재적으로 광범위하게 변하는 메모리 주소로 이동해야하므로 캐시 누락 가능성이 높아집니다.

해시 테이블에 관해서는 여기 StackOverflow에 대한 몇 가지 다른 질문을 읽어야 하지만 여기에서 주요 관심 사항은 다음과 같습니다.

• 해시 테이블은 최악의 경우 O (N)로 저하 될 수 있습니다.
• 해싱 비용은 0이 아니며 일부 구현에서는 특히 문자열의 경우 중요 할 수 있습니다.
• 연결 목록 및 이진 트리에서와 같이 각 항목은 키와 값 이상을 저장 하는 노드 이며 일부 구현에서는 별도로 할당되므로 더 많은 메모리를 사용하고 캐시 미스 가능성을 높입니다.

물론 이러한 데이터 구조의 성능에 대해 정말로 관심이 있다면 테스트해야합니다. 대부분의 일반적인 언어에 대해 이들 중 어느 것이 든 좋은 구현을 찾는 데 거의 문제가 없습니다. 이러한 각 데이터 구조에 실제 데이터 중 일부를 던지고 어떤 것이 가장 잘 수행되는지 확인하는 것이 너무 어렵지 않아야합니다.

1. _{구현시 노드 배열을 미리 할당 할 수 있으며 이는 캐시 미스 문제를 해결하는 데 도움이됩니다. 링크드리스트 나 바이너리 트리의 실제 구현에서는 이것을 본 적이 없습니다 (물론 모든 것을 본 것은 아닙니다). 하지만 노드 객체가 반드시 키 / 값 쌍보다 클 것이기 때문에 캐시 미스 가능성이 약간 더 높습니다 .}

---

나는 Bill의 대답을 좋아하지만 실제로 합성하지는 않습니다.

세 가지 선택에서 :

Linked lists are relatively slow to lookup items from (O(n)). So if you have a lot of items in your table, or you are going to be doing a lot of lookups, then they are not the best choice. However, they are easy to build, and easy to write too. If the table is small, and/or you only ever do one small scan through it after it is built, then this might be the choice for you.

Hash tables can be blazingly fast. However, for it to work you have to pick a good hash for your input, and you have to pick a table big enough to hold everything without a lot of hash collisions. What that means is you have to know something about the size and quantity of your input. If you mess this up, you end up with a really expensive and complex set of linked lists. I'd say that unless you know ahead of time roughly how large the table is going to be, don't use a hash table. This disagrees with your "accepted" answer. Sorry.

That leaves trees. You have an option here though: To balance or not to balance. What I've found by studying this problem on C and Fortran code we have here is that the symbol table input tends to be sufficiently random that you only lose about a tree level or two by not balancing the tree. Given that balanced trees are slower to insert elements into and are harder to implement, I wouldn't bother with them. However, if you already have access to nice debugged component libraries (eg: C++'s STL), then you might as well go ahead and use the balanced tree.

---

A couple of things to watch out for.

• Binary trees only have O(log n) lookup and insert complexity if the tree is balanced. If your symbols are inserted in a pretty random fashion, this shouldn't be a problem. If they're inserted in order, you'll be building a linked list. (For your specific application they shouldn't be in any kind of order, so you should be okay.) If there's a chance that the symbols will be too orderly, a Red-Black Tree is a better option.

• Hash tables give O(1) average insert and lookup complexity, but there's a caveat here, too. If your hash function is bad (and I mean really bad) you could end up building a linked list here as well. Any reasonable string hash function should do, though, so this warning is really only to make sure you're aware that it could happen. You should be able to just test that your hash function doesn't have many collisions over your expected range of inputs, and you'll be fine. One other minor drawback is if you're using a fixed-size hash table. Most hash table implementations grow when they reach a certain size (load factor to be more precise, see here for details). This is to avoid the problem you get when you're inserting a million symbols into ten buckets. That just leads to ten linked lists with an average size of 100,000.

• I would only use a linked list if I had a really short symbol table. It's easiest to implement, but the best case performance for a linked list is the worst case performance for your other two options.

---

Other comments have focused on adding/retrieving elements, but this discussion isn't complete without considering what it takes to iterate over the entire collection. The short answer here is that hash tables require less memory to iterate over, but trees require less time.

For a hash table, the memory overhead of iterating over the (key, value) pairs does not depend on the capacity of the table or the number of elements stored in the table; in fact, iterating should require just a single index variable or two.

For trees, the amount of memory required always depends on the size of the tree. You can either maintain a queue of unvisited nodes while iterating or add additional pointers to the tree for easier iteration (making the tree, for purposes of iteration, act like a linked list), but either way, you have to allocate extra memory for iteration.

But the situation is reversed when it comes to timing. For a hash table, the time it takes to iterate depends on the capacity of the table, not the number of stored elements. So a table loaded at 10% of capacity will take about 10 times longer to iterate over than a linked list with the same elements!

---

This depends on several things, of course. I'd say that a linked list is right out, since it has few suitable properties to work as a symbol table. A binary tree might work, if you already have one and don't have to spend time writing and debugging it. My choice would be a hash table, I think that is more or less the default for this purpose.

---

This question goes through the different containers in C#, but they are similar in any language you use.

---

Unless you expect your symbol table to be small, I should steer clear of linked lists. A list of 1000 items will on average take 500 iterations to find any item within it.

A binary tree can be much faster, so long as it's balanced. If you're persisting the contents, the serialised form will likely be sorted, and when it's re-loaded, the resulting tree will be wholly un-balanced as a consequence, and it'll behave the same as the linked list - because that's basically what it has become. Balanced tree algorithms solve this matter, but make the whole shebang more complex.

A hashmap (so long as you pick a suitable hashing algorithm) looks like the best solution. You've not mentioned your environment, but just about all modern languages have a Hashmap built in.

참고 URL : https://stackoverflow.com/questions/371136/binary-trees-vs-linked-lists-vs-hash-tables