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