哈希表

作者: 升不上三段的大鱼 | 来源:发表于2020-02-19 01:41 被阅读0次

哈希表是一种可以使用关键字(key)来快速查询值的数据结构。每个数据都有它自己的关键字k, 通过哈希函数f(k)处理之后得到一个整数,叫索引值(index)。
想要查找某个关键字对应得值,需要查找哈希函数处理后对应得索引值,以此得到想要得值。
哈希函数简单来说就是取模运算。所以肯定会有不同的关键字得到了相同的索引值的情况,这种情况叫冲突。解决方法有许多,简单来说就是在相同的索引附近找一个空的地方把数据放进去。
哈希表的优点是可以快速查询,平均查找时O(1), 以及关键字能够取很多的数据类型,只要能够用哈希函数。
缺点是在最坏的情况下,需要的时间为O(n);关键字不是按顺序排列的,如果想找个最小或者最大的key对应的值就需要全都找一遍;单项查询,找某个关键字对应的值只需要O(1), 找某个值对应的关键字就要全都找一遍。

C++

// C++ program to demonstrate functionality of unordered_map 
#include <iostream> 
#include <unordered_map> 
using namespace std; 

int main() 
{ 
    // Declaring umap to be of <string, double> type 
    // key will be of string type and mapped value will 
    // be of double type 
    unordered_map<string, double> umap; 
  
    // inserting values by using [] operator 
    umap["PI"] = 3.14; 
    umap["root2"] = 1.414; 
    umap["root3"] = 1.732; 
    umap["log10"] = 2.302; 
    umap["loge"] = 1.0; 

    // inserting value by insert function 
    umap.insert(make_pair("e", 2.718)); 
     
    string key = "PI"; 
    // If key not found in map iterator to end is returned 
    if (umap.find(key) == umap.end()) 
        cout << key << " not found\n\n"; 
    // If key found then iterator to that key is returned 
    else
        cout << "Found " << key << endl;

     // iterating over all value of umap 
    unordered_map<string, double>:: iterator itr; 
    cout << "\nAll Elements : \n"; 
    for (itr = umap.begin(); itr != umap.end(); itr++) 
    { 
        // itr works as a pointer to pair<string, double> 
        // type itr->first stores the key part  and 
        // itr->second stores the value part 
        cout << itr->first << "  " << itr->second << endl; 
     } 
} 

Output:
Found PI

All Elements : 
loge  1
e  2.718
log10  2.302
root3  1.732
PI  3.14
root2  1.414

一个应用: 给定一个字符串,统计里面每个字出现的频率。

// C++ program to find freq of every word using 
// unordered_map 
#include <bits/stdc++.h> 
using namespace std; 
  
// Prints frequencies of individual words in str 
void printFrequencies(const string &str) 
{ 
    // declaring map of <string, int> type, each word 
    // is mapped to its frequency 
    unordered_map<string, int> wordFreq; 
  
    // breaking input into word using string stream 
    stringstream ss(str);  // Used for breaking words 
    string word; // To store individual words 
    while (ss >> word) 
        wordFreq[word]++; 
  
    // now iterating over word, freq pair and printing 
    // them in <, > format 
    unordered_map<string, int>:: iterator p; 
    for (p = wordFreq.begin(); p != wordFreq.end(); p++) 
        cout << "(" << p->first << ", " << p->second << ")\n"; 
} 
  
// Driver code 
int main() 
{ 
    string str = "geeks for geeks geeks quiz "
                 "practice qa for"; 
    printFrequencies(str); 
    return 0; 
} 

Output:
(qa, 1)
(quiz, 1)
(practice, 1)
(geeks, 3)
(for, 2)

代码来源:
GeeksforGeeks--unordered_map in C++ STL

Python

在python里,字典数据类型(Dictionary)用的就是哈希表。

# Declare a dictionary 
dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

# Accessing the dictionary with its key
print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']

Output:
dict['Name']:  Zara
dict['Age']:  7

# Add new entry
dict['School'] = "DPS School"; 

 # remove entry with key 'Name'
del dict['Name'];
# remove all entries in dict
dict.clear();     
 # delete entire dictionary
del dict ;       

应用:
给定一个整数数组 nums 和一个目标值 target,在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

def twoSum(self, nums: List[int], target: int) -> List[int]:
    # Declare an empty dictionary
    dic = {}
    for idx, value in enumerate(nums):
        if target - value in dic:
            return [dic[target-value],idx]
        dic[value] = idx

相关文章

  • Java数据结构_哈希表_基本概念

    本文目标 哈希表的基本概念,哈希冲突,哈希函数 什么是哈希表 哈希表也叫做散列表(hash有剁碎的意思)哈希表是空...

  • redis数据结构--字典

    Redis的字典底层就是哈希表。 哈希表 首先给出哈希表的定义: 其中可以看到,table是一个哈希表节点的数组,...

  • 哈希表和链表

    优秀文章:Chapter: 散列表(哈希表) 一、哈希表 哈希表hashtable(key,value) 就是把K...

  • 算法-哈希表算法总结

    1 哈希表模拟 思路:通过设计哈希表,模拟O(1)时间复杂度的哈希表。 2 数组作为哈希表 思路:数组就是简单的哈...

  • 数据结构 -- 哈希表及其应用

    这篇主要用来记录一下学习到的关于哈希表的知识点。 文章结构 哈希表 哈希表的定义 哈希表的优缺点 哈希碰撞 负载因...

  • 数据结构与算法(第一季):哈希表(Hash Table)

    一、哈希表(Hash Table) 1、概念 哈希表也叫做散列表。 哈希表的原理: 利用哈希函数生成key对应的i...

  • 深入理解哈希表

    深入理解哈希表 深入理解哈希表

  • 2019 算法面试相关(leetcode)--哈希表

    哈希表相关的原理可以参考下:浅谈哈希表(HashTable)深入理解哈希表哈希表的理解理解HashSet及使用 哈...

  • Redis中的字典

    Redis中的字典 Redis中的字典使用哈希表作为底层实现,一个哈希表中可以有多个哈希表结点,而每个哈希表结点保...

  • Redis数据结构与对象——哈希

    1 字典的实现 Redis的字典使用哈希表作为底层实现,一个哈希表可以有多个哈希表节点,即每个哈希表节点就保存了字...

网友评论

      本文标题:哈希表

      本文链接:https://www.haomeiwen.com/subject/rbqofhtx.html