Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 927f7f6

Browse filesBrowse files
bitdovebitdove
committed
Begin HashTable
1 parent 2ec5cbb commit 927f7f6
Copy full SHA for 927f7f6

File tree

Expand file treeCollapse file tree

10 files changed

+124
-0
lines changed
Filter options
Expand file treeCollapse file tree

10 files changed

+124
-0
lines changed

‎README.md

Copy file name to clipboardExpand all lines: README.md
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,8 @@ Remember that each data has its own trade-offs. And you need to pay attention mo
2929
* `B` Doubly Linked List
3030
* `B` [Queue](data-structures/Queue)
3131
* `B` [Stack](data-structures/Stack)
32+
* `B` [Hash Table](data-structures/HashTable)
33+
3234

3335

3436
## Algorithms

‎README.zh-CN.md

Copy file name to clipboardExpand all lines: README.zh-CN.md
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,8 @@
2626
* `B` 双向链表
2727
* `B` [队列](data-structures/Queue)
2828
* `B` [栈](data-structures/Stack)
29+
* `B` [哈希表](data-structures/HashTable)
30+
2931

3032

3133

‎data-structures/HashTable/CMakeLists.txt

Copy file name to clipboard
+21Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# Specify the minimum version of CMake required
2+
cmake_minimum_required(VERSION 3.10)
3+
4+
# Project name and version
5+
project(HashTableProject VERSION 1.0)
6+
7+
# Set C++ standard
8+
set(CMAKE_CXX_STANDARD 11)
9+
set(CMAKE_CXX_STANDARD_REQUIRED True)
10+
11+
# Include directories
12+
include_directories(include)
13+
14+
# Output executables to the 'bin' directory
15+
set(CMAKE_RUNTIME_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/../bin)
16+
17+
# Add the test executable
18+
add_executable(test_HashTable __test__/test_HashTable.cpp)
19+
20+
# Link the HashTable library to the test executable
21+
target_link_libraries(test_HashTable)

‎data-structures/HashTable/README.md

Copy file name to clipboard
+25Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# 哈希表
2+
3+
在计算中, 一个 **哈希表(hash table 或hash map)** 是一种实现 *关联数组(associative array)*
4+
的抽象数据类型, 该结构可以将 *键映射到值*。
5+
6+
哈希表使用 *哈希函数/散列函数* 来计算一个值在数组或桶(buckets)中或槽(slots)中对应的索引,可使用该索引找到所需的值。
7+
8+
理想情况下,散列函数将为每个键分配给一个唯一的桶(bucket),但是大多数哈希表设计采用不完美的散列函数,这可能会导致"哈希冲突(hash collisions)",也就是散列函数为多个键(key)生成了相同的索引,这种碰撞必须
9+
以某种方式进行处理。
10+
11+
12+
![Hash Table](./assets/hash-table.jpeg)
13+
14+
*Made with [okso.app](https://okso.app)*
15+
16+
通过单独的链接解决哈希冲突
17+
18+
![Hash Collision](./assets/collision-resolution.jpeg)
19+
20+
*Made with [okso.app](https://okso.app)*
21+
22+
## 参考
23+
24+
- [Wikipedia](https://en.wikipedia.org/wiki/Hash_table)
25+
- [YouTube](https://www.youtube.com/watch?v=shs0KM3wKv8&index=4&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)

‎data-structures/HashTable/__test__/test_HashTable.cpp

Copy file name to clipboard
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
#include "../include/HashTable.h"

‎data-structures/HashTable/assets/collision-resolution.jpeg

Copy file name to clipboard
261 KB
Loading

‎data-structures/HashTable/assets/hash-table.jpeg

Copy file name to clipboard
161 KB
Loading

‎data-structures/HashTable/build.sh

Copy file name to clipboard
+19Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#!/bin/bash
2+
3+
# Create the build directory if it doesn't exist
4+
if [ ! -d "build" ]; then
5+
mkdir build
6+
fi
7+
8+
# Run CMake in the build directory
9+
cd build
10+
cmake ..
11+
12+
# Build the project using make
13+
make
14+
15+
# Return to the project root directory
16+
cd ..
17+
18+
# Inform the user where the executable can be found
19+
echo "Build complete. Executable located in the ./bin directory."

‎data-structures/HashTable/clean.sh

Copy file name to clipboard
+7Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#!/bin/bash
2+
3+
# Remove build and bin directories
4+
rm -rf build
5+
rm -rf bin
6+
7+
echo "Clean complete. Build and bin directories removed."

‎data-structures/HashTable/include/HashTable.h

Copy file name to clipboard
+47Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
#ifndef HASHTABLE_H
2+
#define HASHTABLE_H
3+
4+
#include "../../Array/include/Vector.h"
5+
#include "../../LinkedList/include/SinglyLinkedList.h"
6+
#include <cstddef>
7+
#include <stdexcept>
8+
9+
const size_t DefautBucketsCounts = 11;
10+
11+
template <typename Key, typename Value>
12+
class HashTable{
13+
public:
14+
HashTable();
15+
~HashTable();
16+
public:
17+
// Capacity
18+
bool empty() {return _size == 0;}
19+
size_t size() {return _size;}
20+
// Element access
21+
Value& at(const Key& key);
22+
Value& operator[](const Key& key);
23+
// Element lookup
24+
size_t count(const Key& key) const;
25+
// Modifiers
26+
void insert(const Key& key, const Value& value);
27+
size_t erase(const Key& key);
28+
void clear();
29+
// Buckets
30+
size_t buckets_count() const;
31+
size_t bucket_size(const size_t n) const;
32+
size_t bucket(const Key& key) const;
33+
private:
34+
struct _KVNode{
35+
Key _key;
36+
Value _value;
37+
};
38+
Vector<SinglyLinkedList<_KVNode>> _buckets;
39+
size_t _size;
40+
};
41+
42+
// Constructor and Destructor
43+
template <typename Key, typename Value>
44+
HashTable<Key, Value>::HashTable() : _buckets(DefautBucketsCounts), _size(0) {}
45+
46+
47+
#endif // HASHTABLE

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.