From dff0972dd98a2a8c46a7bd0bf1308ae06dc670f5 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 4 Feb 2021 21:46:15 +0100 Subject: Fixed a minor API mixup, Docs: open addressing/closed hashing.. --- docs/cmap_api.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'docs') diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 61441fb7..c57dc38f 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -2,7 +2,7 @@ ![Map](pics/map.jpg) A **cmap** is an associative container that contains key-value pairs with unique keys. Search, insertion, -and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. It is implemented as open hashing with linear probing, and without leaving tombstones on erase. +and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. It is implemented as closed hashing (aka open addressing) with linear probing, and without leaving tombstones on erase. See the c++ class [std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map) for a functional description. -- cgit v1.2.3