All geek questions in one place

Effectively insert and search strings

In the application, I will have from 3,000 to 30,000 lines. After creation (reading from files is unordered) there will not be many lines that will be added often (but sometimes it will be!). Deleting rows will also happen infrequently. Comparison of the line with the saved ones will occur frequently.

Which structure can I use best: a hash table, a tree (Red-Black, Splay, ....) or just an ordered list (maybe StringArray?)?

(Additional note: a reference to a good C # implementation will also be appreciated)

+3
source share
5 answers

, -. , HashSet<T> . (, , Dictionary<T> , , .)

HashSet<T> n. , .

  • : O(1), O(n), .
  • : O(1)
  • (): O(1) ( -)

- , - , . - , /- .

+7

HashSet . , O (1).

- , . , , O (n).

HashSet VB 6 ( ) .NET 3.5, , , . , API, .

HashSet, , , . ( ), HashSet . - , . , HashSet .

+4

, . , , .

, , ( , ). - , ( #), , , . , , , , ( , , ).

+2

, HashSet<T>, , " ". IEqualityComparer<string> (, StringComparer) ..

, , , " , ?" , , , . (List<T> BinarySearch, , SortedList SortedDictionary , . , SortedDictionary , , , , , .)

, " ", HashSet<T> - . , :)

+1

" , " ( ), trie. "" , "" , . - .

N = 30 000 , . , k * N Optional k ( , , . " ", , O (n), , O (n) , " " . , /.

+1
source

Source: https://habr.com/ru/post/1710915/

More articles:


All Articles