# Data scructures ## Linear * Array * Linked List * Circular Linked List --- ### Stack LIFO  --- #### Operations * Push * Pop #### Where to use Simple and fast. Нединамическая память. --- #### Where `cmd/jumps/prints/constructor_and_var.print` `core/vm/stack.go` --- ### Queue первый пришёл — первый вышел  --- #### Operations * добавление элемента (enqueue) возможно лишь в конец очереди * убрать из начала очереди(dequeue) #### Where to use Элементы с отношением порядка: по порядковому номеру или по времени создания/поступления Очередь запросов на обработку, блоков на добавление, транзакций для валидации. --- #### Where Priority queue - добавляется операция извлечения максимума. Where: `common/prque/prque.go` `p2p/discv5/topic.go:375` --- ## Trees ### Binary Tree  --- #### Operations FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K. INSERT(K, V) — добавление в дерево пары (key, value) = (K, V). REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K. #### Where `p2p/dnsdisc/tree.go` DB --- ### Binary Search Tree * Оба поддерева — левое и правое — являются двоичными деревьями поиска. * У всех узлов левого поддерева произвольного узла X значения ключей данных меньше либо равны, нежели значение ключа данных самого узла X. * У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X. --- #### Operations FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K. INSERT(K, V) — добавление в дерево пары (key, value) = (K, V). REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K. --- #### Where to use Хотим быстрый поиск и сортировку. Проблема сортировки. Частичная сортировка. #### Where DB --- ### Heap Full binary tree+sort function  --- #### Operations * найти максимум или найти минимум: найти максимальный элемент в max-куче или минимальный элемент в min-куче, соответственно * удалить максимум или удалить минимум: удалить корневой узел в max- или min-куче, соответственно * добавить: добавление нового ключа в кучу * слияние: соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных. --- #### Where to use Something sorted with Add and Remove operations as well #### Where `core/tx_list.go` `core/types/transaction.go:352` --- * Prefix tree  `cmd/jumps/contract_runner.go:25` --- ## Probability ### Bloom filter Membership  --- False positive is possible when the queried positions are already set to 1. But false negative is impossible. Memory and false positive probability are configurable. Query time is O(k). Union and intersection of bloom filters with same size and hash functions can be implemented with bitwise OR and AND operations. Cannot remove an element from the set (counting bloom filter can) --- #### Where `core/types/bloom9.go:103` --- ### HyperLogLog Хотим знать число уникальных элементов. Для set - это cardinality. Элементов ОЧЕНЬ много, на все памяти не хватит. "The HyperLogLog algorithm is able to estimate cardinalities of > 109 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory." --- "The basis of the HyperLogLog algorithm is the observation that the cardinality of a multiset of uniformly distributed random numbers can be estimated by calculating the maximum number of leading zeros in the binary representation of each number in the set. If the maximum number of leading zeros observed is n, an estimate for the number of distinct elements in the set is 2^n" Add, count, merge --- ### Count–min sketch Frequency  --- * Union can be performed by cell-wise ADD operation * O(k) query time * Better accuracy for higher frequency items (heavy hitters) * Can only cause over-counting but not under-counting --- ## Distributed ### DHT https://en.wikipedia.org/wiki/Distributed_hash_table