精华内容
下载资源
问答
  • 哈希表时间复杂度

    千次阅读 2020-12-27 17:58:05
    哈希表 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来...哈希表 是使用 O(1)O(1)时间复杂度 进行数据的插入删除和查找,但

    哈希表

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

    哈希表 是使用 O(1)O(1)时间复杂度 进行数据的插入删除和查找,但是哈希表不保证表中数据的有序性,这样在哈希表中查找最大数据或者最小数据的时间是 O(N)O(N) 实现。

    复杂度

    时间复杂度:O(n),其中 n 为字符串的长度。我们只需同时遍历一遍字符串 s和 t 即可。
    空间复杂度:O(∣Σ∣),其中 Σ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小,最坏情况下每个字符均不相同,需要 O(∣Σ∣) 的空间。

    基本概念

    • 若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。
    • 对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为冲突(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数 f(k)处理冲突 的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
    • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

    常用方法

    散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。
    实际工作中需视不同的情况采用不同的哈希函数,通常考虑的因素有:

    • 计算哈希函数所需时间

    • 关键字的长度

    • 哈希表的大小

    • 关键字的分布情况

    • 记录的查找频率

      1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。若其中H(key)中已经有值了,就往下一个找,直到H(key)中没有值了,就放进去。

    1. 数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

    2. 平方取中法:当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。
      例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址.

    3. 折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    4. 随机数法:选择一随机函数,取关键字的随机值作为散列地址,即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。

    5. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。 [2]

    展开全文
  • 哈希表时间复杂度分析 n个元素平均的分布在M棵红黑树中,每棵红黑树容纳的元素平均为 n/M ,即现有的哈希表时间复杂度为O(log(n/M)); 说好的O(1)呢? M越大,元素分散的越平均,时间复杂度越低,M足够大,...

    哈希表的时间复杂度分析

    • n个元素平均的分布在M棵红黑树中,每棵红黑树容纳的元素平均为 n/M ,即现有的哈希表的时间复杂度为O(log(n/M));
    • 说好的O(1)呢?
    • M越大,元素分散的越平均,时间复杂度越低,M足够大,时间复杂度理论上就可以达到O(1);

    动态扩容代码

    • 触发扩容,缩容的上界和哈希表的初始容量;
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private static final int initCapacity = 7;
    
    public HashTable(){
        this(initCapacity);
    }
    
    • 添加元素时扩容
    public void add(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key))
            map.put(key, value);
        else{
            map.put(key, value);
            size ++;
    
            if(size >= upperTol * M)
                resize(2 * M);
        }
    }
    
    • 删除元素时缩容
    public V remove(K key){
        V ret = null;
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key)){
            ret = map.remove(key);
            size --;
    
            if(size < lowerTol * M && M / 2 >= initCapacity)
                resize(M / 2);
        }
        return ret;
    }
    
    • 容量调整代码
      • 复制时的遍历,遍历的是老哈希表,老的M值要先存下来;
      • 复制的时候元素的key值重新计算hash值要用新的M值,要将this.M更新过来;
    private void resize(int newM){
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for(int i = 0 ; i < newM ; i ++)
            newHashTable[i] = new TreeMap<>();
    
        int oldM = M;
        this.M = newM;
        for(int i = 0 ; i < oldM ; i ++){
            TreeMap<K, V> map = hashtable[i];
            for(K key: map.keySet())
                newHashTable[hash(key)].put(key, map.get(key));
        }
    
        this.hashtable = newHashTable;
    }
    

    速度比较

    import java.util.ArrayList;
    
    public class Main {
    
        public static void main(String[] args) {
            System.out.println("Pride and Prejudice");
            ArrayList<String> words = new ArrayList<>();
            if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
                System.out.println("Total words: " + words.size());
    
                // Test BST
                long startTime = System.nanoTime();
    
                BST<String, Integer> bst = new BST<>();
                for (String word : words) {
                    if (bst.contains(word))
                        bst.set(word, bst.get(word) + 1);
                    else
                        bst.add(word, 1);
                }
    
                for(String word: words)
                    bst.contains(word);
    
                long endTime = System.nanoTime();
                double time = (endTime - startTime) / 1000000000.0;
                System.out.println("BST: " + time + " s");
    
    
                // Test AVL
                startTime = System.nanoTime();
    
                AVLTree<String, Integer> avl = new AVLTree<>();
                for (String word : words) {
                    if (avl.contains(word))
                        avl.set(word, avl.get(word) + 1);
                    else
                        avl.add(word, 1);
                }
    
                for(String word: words)
                    avl.contains(word);
    
                endTime = System.nanoTime();
                time = (endTime - startTime) / 1000000000.0;
                System.out.println("AVL: " + time + " s");
    
    
                // Test RBTree
                startTime = System.nanoTime();
    
                RBTree<String, Integer> rbt = new RBTree<>();
                for (String word : words) {
                    if (rbt.contains(word))
                        rbt.set(word, rbt.get(word) + 1);
                    else
                        rbt.add(word, 1);
                }
    
                for(String word: words)
                    rbt.contains(word);
    
                endTime = System.nanoTime();
                time = (endTime - startTime) / 1000000000.0;
                System.out.println("RBTree: " + time + " s");
    
    
                // Test HashTable
                startTime = System.nanoTime();
    
                HashTable<String, Integer> ht = new HashTable<>();
                //HashTable<String, Integer> ht = new HashTable<>(131071);
                for (String word : words) {
                    if (ht.contains(word))
                        ht.set(word, ht.get(word) + 1);
                    else
                        ht.add(word, 1);
                }
    
                for(String word: words)
                    ht.contains(word);
    
                endTime = System.nanoTime();
                time = (endTime - startTime) / 1000000000.0;
                System.out.println("HashTable: " + time + " s");
            }
    
            System.out.println();
        }
    }
    

    输出:

    • 哈希表还是要快一点的;

    Pride and Prejudice
    Total words: 125901
    BST: 0.1321059 s
    AVL: 0.1091658 s
    RBTree: 0.107052 s
    HashTable: 0.1011918 s

    展开全文
  • 1.提目描述: 给定一个整数数组 nums和一个整数目标值 target,请你在该数组中找出 和为目标值 target的那两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。...使用哈希表,...

    1.提目描述:

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

    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

    你可以按任意顺序返回答案。

     

     

    2.思路: 

    注意到全部遍历的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。

    使用哈希表,可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)。

    这样我们创建一个哈希表,对于每一个 x,我们首先查询哈希表中是否存在 target - x,若不存在将 x 插入到哈希表中,即可保证不会让 x 和自己匹配。

    3.代码: 

    #include<iostream>
    #include<unordered_map>
    #include<vector>
    using namespace std;
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;//第一个int储存数值,第二个是下表
        for (int i = 0; i < nums.size(); ++i) {
            unordered_map<int, int>::const_iterator it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {//若找到就返回下标,往前找
                return { it->second, i };
            }
            hashtable[nums[i]] = i;//将当前的放进去表
        }
        return {};
    }
    int main() {
        vector<int> arr;
        arr.push_back(3);
        arr.push_back(2);
        arr.push_back(2);
        arr.push_back(5);
        arr.push_back(5);
        vector<int>ans = twoSum(arr, 4);
        cout << ans[0] << " " << ans[1] << endl;
    
    }

    展开全文
  • // 使用hashmap代表多重集,(合并处理和查询)降低查询时间复杂度 int n = A.size(); // 个人认为m是value_initialized的理由是一开始没法初始化 unordered_map, int> m; // 第一个元素代表元素值,第二个元素...

    问题描述:

    给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0

    为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间,最终结果不会超过 231 - 1 。

    例如:

    输入:
    A = [ 1, 2]
    B = [-2,-1]
    C = [-1, 2]
    D = [ 0, 2]
    
    输出:
    2
    
    解释:
    两个元组如下:
    1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
    

    基本思路:

    这道题暴力O(n^4), 绝对不可取。于是采用二分的技巧

    遍历前两个列表,获得所有两个数的和;遍历后两个列表,获得所有数的两个和;统计这两个结果集中互为相反数的元素个数,即为答案。

    这样我们的复杂度就降为O(n^2)了。

    不过还是TLE了,于是我们想到用哈希表的思想来降低复杂度。

    这是因为哈希表插入和查询一个元素的平均时间复杂度为O(1);

    (其它的,如BST,插入和查询都是O(logn),普通的vector,插入时O(1), 查询时O(n))

    同时我们可以通过获得元素和后马上查询的方式减少代码量

    AC代码:

    class Solution {
    public:
        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
          // 二分法降低复杂度
          // 使用hashmap代表多重集,(合并处理和查询)降低查询时间复杂度
          int n = A.size(); 
          // 个人认为m是value_initialized的理由是一开始没法初始化
          unordered_map<int, int> m;    // 第一个元素代表元素值,第二个元素代表重复的次数
          for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
              ++m[A[i] + B[j]];
            }
          }
          int count = 0;
          for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
              count += m[-C[i] - D[j]];
            }
          }
          return count;
        }
    };

    其它经验:

    1.  不得不说我儿子说得还是很有道理,map确实比unordered_map慢太多了
    2. 如果我们有必要使用多重集,完全可以通过用unorder_map来模拟,其key对应的value是元素重复的个数。
    3. 如果元素在处理后要匹配,完全可以通过边处理边匹配的方式来降低复杂度
    展开全文
  • 1 哈希表复杂度分析(链地址法) 一共有 M 个地址,如果放入的总元素个数是 N 如果每个地址是链表,O(N / M) 如果每个地址是平衡树:O(log( N / M)) 2 哈希表的动态空间处理 当平均每个地址承载的元素超过一定...
  • 哈希表的最差复杂度是n2Prerequisite: 先决条件: Hashing data structure 散列数据结构 Problem statement: 问题陈述: Given an array and a sum X, fins any pair which sums to X. Expected time complexity...
  • 哈希算法和时间复杂度

    万次阅读 2019-03-04 15:26:35
    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间...
  • Redis底层详解(一) 哈希表和字典

    万次阅读 多人点赞 2018-06-28 17:27:37
    一文读懂哈希表
  • O(logn) – O(logn) O(logn) 二叉树(最坏情况) O(n) – O(n) O(n) 平衡树 O(logn) O(logn) O(logn) O(logn) 排序二叉树 O(logn)~O(n) O(logn)~O(n) O(logn)~O(n) O(logn)~O(n) 哈希表 O(1) – O(1) O(1)
  • 无序数组直接插在末尾,时间复杂度为1 有序数组使用二分查找,时间复杂度logN 无序链表插入在表尾,时间复杂度1 有序链表插入需要寻找插入位置,时间复杂度N 二叉树一般情况即为平衡二叉树,最坏情况为有序链表 不过...
  • 哈希表的插入和删除平均时间为什么是O(1)? 末尾的插入和删除是O(1),最坏情况的插入删除是O(n),那平均为什么还是O(1)呢? 看了几篇文章,隐约有了答案,但还不是很确定。可能这是文字上的一种理解问题。 我...
  • 二分法搜索与哈希表

    2019-05-30 16:20:49
    在寻找排序数组中的某一个数字的时候可以使用二分法与哈希表的方式,哈希表时间复杂度是o(1),但是空间复杂度增大了,需要把所有存入哈希表内,而二分法就比较简单了,只需要进行折半查找。 哈希表: 从头到尾遍历...
  • python-哈希查找-时间复杂度O(1)

    千次阅读 2018-08-27 17:54:15
    哈希查找是通过计算数据元素的存储地址进行查找的一种方法。 比如”5“是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个”2”,那么此时的”5“和“2”就建立一种对应关系,这种关系就是所谓的“哈希...
  • 哈希类型的内部编码有两种: ziplist(压缩列表): 当哈希类型元素个数小于hash-max-ziplist-entries配置(默认512个) 、 同时...hashtable(哈希表): 当哈希类型无法满足ziplist的条件时, Redis会使用hasht...
  • 哈希表

    2021-01-02 15:25:15
    哈希表时间复杂度O(1) 哈希表的样式 数组就是哈希表 下标就是哈希表的索引 数组元素就是哈希表的数字 哈希函数 通过hashCode把名字转化为数值,hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,...
  • 哈希表减少时间复杂原理的总结 哈希表相当于一个容器,能够将类似数组的存储起来,key/value形式,哈希表减少复杂度的例子如下: 问题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的...
  • 这种题目要么两重循环时间复杂度On^2空间复杂度O1,要么用哈希表时间复杂度On空间复杂度On。 基本思想:哈希表+贪心,先遍历一遍num,将num每一位上的数字用哈希表记录下标,然后再遍历一遍num,如果当前位上的数...
  • 无序数组直接插在末尾,时间复杂度为1 有序数组使用二分查找,时间复杂度logN 无序链表插入在表尾,时间复杂度1 有序链表插入需要寻找插入位置,时间复杂度N 二叉树一般情况即为平衡二叉树,最坏情况为有序链表 ...
  • 哈希表中查找一个key的时间复杂度到底是多少?–leetcode 1 不出意外的话,这应该是我的第一篇博客。 今天下午上课,听的东西完全不进脑子,状态奇差(不过好像很多课我都这样),于是打开几个月没碰的...
  • 一、哈希表1、概念 哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数...
  • 目录题目描述思路题解方法一:仿哈希表方法二:置换法 题目描述 https://leetcode-cn.com/problems/first-missing-positive/ 思路题解 ...方法一:仿哈希表 时间复杂度 :O(3N)=O(N) 空间复杂度:O(1) class
  • C++或者Java无序关联容器底层采用链式哈希表实现 为什么不采用线性探测哈希表? 如果采用线性探测哈希表,缺陷是: 1、发生哈希冲突时,需要从当前发生哈希冲突的位置向后不断的去找,找到第一个空闲的位置把元素放...
  • 哈希表(一)——哈希表的大小

    万次阅读 多人点赞 2018-08-30 13:47:27
    哈希表的设计主要是为了查找,为了对内存中的数据进行快速查找,它的查找时间复杂度是O(1)。设计一个哈希表的关键有三个:怎么控制哈希表的长度,怎么设计哈希函数,怎么处理哈希冲突 今天这篇文章先来讨论一下...
  • 【问题描述】[中等] 【解答思路】 141 每次遍历到一个节点时,判断该节点此前是否被访问过。...时间复杂度:O(N) 空间复杂度:O(N) public class Solution { public boolean hasCycle(ListNode head) {
  • 数据结构的核心思想是通过数据结构的思维来优化代码的算法,以此来提升程序的执行性能,缩短程序执行的时间。下面我来举两个例子,以此来说明数据结构的时间复杂度计算问题。
  • 如果采用链地址法来存储元素的话,如果哈希表有M个地址,如果要想放入哈希表的元素为N。 问题: 那么此时每个地址就能存储M/N个元素。此时它们的哈希值是冲突的。 如果每个地址都存储的是链表:O(N/M) 如果...
  • 哈希表 01 哈希表基础

    2019-02-24 15:35:00
    哈希表 哈希函数:将“键”转换为“索引”,键可能是字符串,浮点数,日期等; 通常情况下很难保证每一个“键”通过哈希函数的转换对应... 如果我们有1的空间,我们只能用O(n)的时间复杂度完成各项操作(线性表...
  • 假如有10000000个数据,数据的大小范围在0-100,那么我们只需要遍历一遍数组,然后记录个数,再根据哈希表输出,这个时候我们使用哈希桶排所用的时间复杂度可以近似的为O(n)级别。 leetCode第一题:

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 72,436
精华内容 28,974
关键字:

哈希表时间复杂度