key值最多膨胀64倍,查找时间复杂度为len(key)*4的hash_map

作者：传说中DE神 | 来源：互联网 | 2023-06-07 19:56

常用的字符串hash算法是根据字符串算出一个整数，再根据这个整数进行存储(http:blog.csdn.netdjinglanarticledetails8812934)，而整数的hash

常用的字符串hash算法是根据字符串算出一个整数，再根据这个整数进行存储(http://blog.csdn.net/djinglan/article/details/8812934)，而整数的hash一般是定义一个很大的空间，而进行一次性hash，浪费空间很严重，而且计算出来的整数不能保证唯一性，有可能是重复的。

根据key，value的特性，我设计了一种新的方式去定位字符串，这种方法所需要的空间不是很大，每个key都有唯一，查找复杂度也是固定不变的，就是key的长度。

首先：
一个字节的范围0~255，对字节进行编码，最简单的是256进制编码，一个256的数组，字节就可以直接定位了，例如：


struct node{
        void * node[256] 
    };
    node head;
    char * key = "sdada";
    char * p = key;
    node * pnode = &head;
    void * data = 0;
    do{
        unsigned char c = p[0];
        data = pnode->node[c];
        p++;
        if (!p[0]){ break;}
        pnode = (node*)data;
    }while(false);

当然实际中，会比这段代码复杂，需要将键值和数据分开。
key = "sdada"只要查找5次就能找到值了，这里有个缺点一个字节膨胀了256*4 = 1024倍。即膨胀系数为1024

256是16的平方倍数，我们可以用16进制编码：

struct node{
        void * node[16] 
    };
    node head;
    char * key = "sdada";
    char * p = key;
    node * pnode = &head;
    void * data = 0;
    do{
        unsigned char c = p[0];
        int index1 = c/16;
        int index2 = c%16;
        pnode = (node*)pnode->node[index1];
        data =  (node*)pnode->node[index2];
        p++;
        if (!p[0]){ break;}
        pnode = (node*)data;
    }while(false);

进行16进制编码后，发现字节膨胀系数变成（16+16）*4 = 128，膨胀系数128比1024少了许多，只是查找次数是256编码的2倍，但是这是可以接受的。
后面还实验了对字节进行4进制编码：
结果：膨胀系数为（4+4+4+4）*4 = 64 ，查找次数为16进制的2倍，256进制的4倍
2进制编码：
结果：膨胀系数为（2+2+2+2+2+2+2+2）*4 = 64 与4进制相同，查找次数为4进制的2倍，256进制的8倍。
这种几种编码还有一种因素，那就是节点复用率，经测试发现，节点复用率 2进制编码》4进制编码 =》16进制编码 =》256进制编码。

测试例子：


time_t t = time(0);
    hdc_hash_map map;
    for (int i = 0; i <1000000; i++)
    {
        int sas = i;
        map.set((const char*)(&sas),sizeof(int),0);
    }
   printf("%ld\n",time(0)-t);

100万个key, 每个key长度为4字节，用4进制编码进行hash，计算需要（1000000*64*4）= 244M的空间，实际占用108M，花费时间2s时间。

我个人建议：对字符进行4进制编码，进行hash最划算，膨胀系数：64，查找次数为key长度的4倍，还有节点复用率也不错，具体需要做详细测试。

3 个解决方案

#1

搜“暴雪哈希算法”

#2

在网上查了资料，与我介绍的这种不同吧，我设计的是一种树形的存储结构：

，每棵字节树含有256个节点，data节点后面再接入下一个字节树，数据存储的时候按照规则建树，查询的时候只要按照规则查询就行了。

#3

static int hdc_pe4[256][4] = {
    {0,0,0,0},{0,0,0,1},{0,0,0,2},{0,0,0,3},
    {0,0,1,0},{0,0,1,1},{0,0,1,2},{0,0,1,3},
    {0,0,2,0},{0,0,2,1},{0,0,2,2},{0,0,2,3},
    {0,0,3,0},{0,0,3,1},{0,0,3,2},{0,0,3,3},
    {0,1,0,0},{0,1,0,1},{0,1,0,2},{0,1,0,3},
    {0,1,1,0},{0,1,1,1},{0,1,1,2},{0,1,1,3},
    {0,1,2,0},{0,1,2,1},{0,1,2,2},{0,1,2,3},
    {0,1,3,0},{0,1,3,1},{0,1,3,2},{0,1,3,3},
    {0,2,0,0},{0,2,0,1},{0,2,0,2},{0,2,0,3},
    {0,2,1,0},{0,2,1,1},{0,2,1,2},{0,2,1,3},
    {0,2,2,0},{0,2,2,1},{0,2,2,2},{0,2,2,3},
    {0,2,3,0},{0,2,3,1},{0,2,3,2},{0,2,3,3},
    {0,3,0,0},{0,3,0,1},{0,3,0,2},{0,3,0,3},
    {0,3,1,0},{0,3,1,1},{0,3,1,2},{0,3,1,3},
    {0,3,2,0},{0,3,2,1},{0,3,2,2},{0,3,2,3},
    {0,3,3,0},{0,3,3,1},{0,3,3,2},{0,3,3,3},
    {1,0,0,0},{1,0,0,1},{1,0,0,2},{1,0,0,3},
    {1,0,1,0},{1,0,1,1},{1,0,1,2},{1,0,1,3},
    {1,0,2,0},{1,0,2,1},{1,0,2,2},{1,0,2,3},
    {1,0,3,0},{1,0,3,1},{1,0,3,2},{1,0,3,3},
    {1,1,0,0},{1,1,0,1},{1,1,0,2},{1,1,0,3},
    {1,1,1,0},{1,1,1,1},{1,1,1,2},{1,1,1,3},
    {1,1,2,0},{1,1,2,1},{1,1,2,2},{1,1,2,3},
    {1,1,3,0},{1,1,3,1},{1,1,3,2},{1,1,3,3},
    {1,2,0,0},{1,2,0,1},{1,2,0,2},{1,2,0,3},
    {1,2,1,0},{1,2,1,1},{1,2,1,2},{1,2,1,3},
    {1,2,2,0},{1,2,2,1},{1,2,2,2},{1,2,2,3},
    {1,2,3,0},{1,2,3,1},{1,2,3,2},{1,2,3,3},
    {1,3,0,0},{1,3,0,1},{1,3,0,2},{1,3,0,3},
    {1,3,1,0},{1,3,1,1},{1,3,1,2},{1,3,1,3},
    {1,3,2,0},{1,3,2,1},{1,3,2,2},{1,3,2,3},
    {1,3,3,0},{1,3,3,1},{1,3,3,2},{1,3,3,3},
    {2,0,0,0},{2,0,0,1},{2,0,0,2},{2,0,0,3},
    {2,0,1,0},{2,0,1,1},{2,0,1,2},{2,0,1,3},
    {2,0,2,0},{2,0,2,1},{2,0,2,2},{2,0,2,3},
    {2,0,3,0},{2,0,3,1},{2,0,3,2},{2,0,3,3},
    {2,1,0,0},{2,1,0,1},{2,1,0,2},{2,1,0,3},
    {2,1,1,0},{2,1,1,1},{2,1,1,2},{2,1,1,3},
    {2,1,2,0},{2,1,2,1},{2,1,2,2},{2,1,2,3},
    {2,1,3,0},{2,1,3,1},{2,1,3,2},{2,1,3,3},
    {2,2,0,0},{2,2,0,1},{2,2,0,2},{2,2,0,3},
    {2,2,1,0},{2,2,1,1},{2,2,1,2},{2,2,1,3},
    {2,2,2,0},{2,2,2,1},{2,2,2,2},{2,2,2,3},
    {2,2,3,0},{2,2,3,1},{2,2,3,2},{2,2,3,3},
    {2,3,0,0},{2,3,0,1},{2,3,0,2},{2,3,0,3},
    {2,3,1,0},{2,3,1,1},{2,3,1,2},{2,3,1,3},
    {2,3,2,0},{2,3,2,1},{2,3,2,2},{2,3,2,3},
    {2,3,3,0},{2,3,3,1},{2,3,3,2},{2,3,3,3},
    {3,0,0,0},{3,0,0,1},{3,0,0,2},{3,0,0,3},
    {3,0,1,0},{3,0,1,1},{3,0,1,2},{3,0,1,3},
    {3,0,2,0},{3,0,2,1},{3,0,2,2},{3,0,2,3},
    {3,0,3,0},{3,0,3,1},{3,0,3,2},{3,0,3,3},
    {3,1,0,0},{3,1,0,1},{3,1,0,2},{3,1,0,3},
    {3,1,1,0},{3,1,1,1},{3,1,1,2},{3,1,1,3},
    {3,1,2,0},{3,1,2,1},{3,1,2,2},{3,1,2,3},
    {3,1,3,0},{3,1,3,1},{3,1,3,2},{3,1,3,3},
    {3,2,0,0},{3,2,0,1},{3,2,0,2},{3,2,0,3},
    {3,2,1,0},{3,2,1,1},{3,2,1,2},{3,2,1,3},
    {3,2,2,0},{3,2,2,1},{3,2,2,2},{3,2,2,3},
    {3,2,3,0},{3,2,3,1},{3,2,3,2},{3,2,3,3},
    {3,3,0,0},{3,3,0,1},{3,3,0,2},{3,3,0,3},
    {3,3,1,0},{3,3,1,1},{3,3,1,2},{3,3,1,3},
    {3,3,2,0},{3,3,2,1},{3,3,2,2},{3,3,2,3},
    {3,3,3,0},{3,3,3,1},{3,3,3,2},{3,3,3,3}
};

这是每个字节固定的查找或者建树的规则。

推荐阅读

string
[大整数乘法] java代码实现

本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]

蜡笔小新 2023-12-13 11:21:32
post
java 模拟get post请求_Java后台模拟发送http的get和post请求，并测试

个人学习使用：谨慎参考1Client类importcom.thoughtworks.gauge.Step;importcom.thoughtworks.gauge.T ... [详细]

蜡笔小新 2023-12-13 14:20:23
数组
JDK源码学习之HashTable(附带面试题)的学习笔记

本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记，包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货，并附带了其他相关主题的学习笔记。 ... [详细]

蜡笔小新 2023-12-12 13:05:17
python
模板引擎StringTemplate的使用方法和特点

本文介绍了模板引擎StringTemplate的使用方法和特点，包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时，还介绍了StringTemplate语法中的属性和普通字符的使用方法，并提供了向模板填充属性的示例代码。 ... [详细]

蜡笔小新 2023-12-11 21:45:03
string
获取当前模块所在路径的GetModuleFileName函数用法详解

本文详细介绍了GetModuleFileName函数的用法，该函数可以用于获取当前模块所在的路径，方便进行文件操作和读取配置信息。文章通过示例代码和详细的解释，帮助读者理解和使用该函数。同时，还提供了相关的API函数声明和说明。 ... [详细]

蜡笔小新 2023-12-14 19:29:57
string
电话号码的字母组合解题思路和代码示例

本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法，可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]

蜡笔小新 2023-12-14 18:50:22
string
SpringBoot uri统一权限管理的实现方法及步骤详解

本文详细介绍了SpringBoot中实现uri统一权限管理的方法，包括表结构定义、自动统计URI并自动删除脏数据、程序启动加载等步骤。通过该方法可以提高系统的安全性，实现对系统任意接口的权限拦截验证。 ... [详细]

蜡笔小新 2023-12-14 16:11:30
string
如何在有序字符序列中插入新字符并保持有序

本文介绍了如何在给定的有序字符序列中插入新字符，并保持序列的有序性。通过示例代码演示了插入过程，以及插入后的字符序列。 ... [详细]

蜡笔小新 2023-12-14 11:16:33
string
Spring特性实现接口多类的动态调用详解

本文详细介绍了如何使用Spring特性实现接口多类的动态调用。通过对Spring IoC容器的基础类BeanFactory和ApplicationContext的介绍，以及getBeansOfType方法的应用，解决了在实际工作中遇到的接口及多个实现类的问题。同时，文章还提到了SPI使用的不便之处，并介绍了借助ApplicationContext实现需求的方法。阅读本文，你将了解到Spring特性的实现原理和实际应用方式。 ... [详细]

蜡笔小新 2023-12-14 03:24:19
string
开发笔记:Java是如何读取和写入浏览器Cookies的

篇首语：本文由编程笔记#小编为大家整理，主要介绍了Java是如何读取和写入浏览器Cookies的相关的知识，希望对你有一定的参考价值。首先我 ... [详细]

蜡笔小新 2023-12-12 20:18:02
default
深入浅出Linux设备驱动编程的重要性与方法

本文介绍了深入浅出Linux设备驱动编程的重要性，以及两种加载和删除Linux内核模块的方法。通过一个内核模块的例子，展示了模块的编译和加载过程，并讨论了模块对内核大小的控制。深入理解Linux设备驱动编程对于开发者来说非常重要。 ... [详细]

蜡笔小新 2023-12-12 15:28:09
string
PHP调用实现波场交互[支持TRX/TRC20]的开发包

本文介绍了一个适用于PHP应用快速接入TRX和TRC20数字资产的开发包，该开发包支持使用自有Tron区块链节点的应用场景，也支持基于Tron官方公共API服务的轻量级部署场景。提供的功能包括生成地址、验证地址、查询余额、交易转账、查询最新区块和查询交易信息等。详细信息可参考tron-php的Github地址：https://github.com/Fenguoz/tron-php。 ... [详细]

蜡笔小新 2023-12-11 17:02:09
string
Java面经整理及相关概念解析

本文整理了Java面试中常见的问题及相关概念的解析，包括HashMap中为什么重写equals还要重写hashcode、map的分类和常见情况、final关键字的用法、Synchronized和lock的区别、volatile的介绍、Syncronized锁的作用、构造函数和构造函数重载的概念、方法覆盖和方法重载的区别、反射获取和设置对象私有字段的值的方法、通过反射创建对象的方式以及内部类的详解。 ... [详细]

蜡笔小新 2023-12-10 22:17:08
string
HashMap的相关问题及其底层数据结构和操作流程

本文介绍了关于HashMap的相关问题，包括其底层数据结构、JDK1.7和JDK1.8的差异、红黑树的使用、扩容和树化的条件、退化为链表的情况、索引的计算方法、hashcode和hash()方法的作用、数组容量的选择、Put方法的流程以及并发问题下的操作。文章还提到了扩容死链和数据错乱的问题，并探讨了key的设计要求。对于对Java面试中的HashMap问题感兴趣的读者，本文将为您提供一些有用的技术和经验。 ... [详细]

蜡笔小新 2023-12-10 17:07:36
string
Hibernate延迟加载深入分析-集合属性的延迟加载策略

本文深入分析了Hibernate延迟加载的机制，特别是集合属性的延迟加载策略。通过延迟加载，可以降低系统的内存开销，提高Hibernate的运行性能。对于集合属性，推荐使用延迟加载策略，即在系统需要使用集合属性时才从数据库装载关联的数据，避免一次加载所有集合属性导致性能下降。 ... [详细]

蜡笔小新 2023-12-10 14:26:13

传说中DE神

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章