文档章节

C++和Java HashMap,HashSet

精神病的羽毛球
 精神病的羽毛球
发布于 2014/04/01 23:57
字数 325
阅读 203
收藏 0

    上次跟一阿里的前辈交流,他问我对Java的HashMap熟不熟悉,我很汗颜,告诉他我一直都在用C++的stl。他又接着问我C++的HashMap是用什么数据结构实现的?我想了半天,STL里面map和multiMap我倒是经常用,HashMap没用过,不是特别肯定的告诉他是“红黑树”。

    今天突然想起,上网搜了一下,原来标准std中并没有实现HashMap,gnu c++提供了hash_map。标准std中的Map确实是基于红黑树,添加和删除都是O(log(n));gnu的hash_map查找和添加复杂 度均为O(1)。Java中的HashMap是基于数组和链地址法实现,添加和删除复杂度也O(1)。

    Java HashSet也是中Hash结构,底层是基于HashMap实现。

    HashSet派生自AbstractSet,实现了Set接口。它有两个私有成员:

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    其中map就是set的底层实现,但只用到了map中的key,map中的value就是这个PRESENT。

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    还有一点需要注意的是,HashSet底层也可以基于LinkedHashMap实现:

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    

    

© 著作权归作者所有

精神病的羽毛球
粉丝 2
博文 27
码字总数 20242
作品 0
成都
程序员
私信 提问
加载中

评论(1)

pww71
pww71
https://sourceforge.net/projects/pwwhashmap/?source=navbar
向你推荐一下新的map算法
cxxJava -- 像Java一样开发C++

cxxJava -- 像Java一样开发C++ 当你同时有过java和c++两个语言的开发经历后,你会喜欢上java语言开发效率的高效但又深深的被c++语言运行效率的高效所吸引。 java类库的丰富性、通用性、易用性...

cxxjava
2016/12/12
175
0
Thrift RPC 系列教程(1)——Thrift语言

Thrift不是严格意义上的编程语言,但是却胜过很多编程语言,充满了美感。 基础数据类型 Thrift 这门编程语言提供了如下几种基础的数据类型: bool: A boolean value (true or false) byte: ...

浮生若梦的编程
2018/11/05
0
0
cocos2d-x中通过Jni实现Java与C++的互相调用

cocos2d-x中通过Jni实现Java与C++的互相调用。 cocos2d-x用开发者提供了一个类JniHelper,提供了java与c++之间互调的jni解决方案。 笔者所开发的“史上最坑爹的游戏”项目中使用到了JNI,为此...

MingliC
2013/12/23
9.3K
2
JNI和NDK的区别

NDK(Native Development Kit)“原生”也就是二进制 android常用的开发方式是java封装的库,而这些库的底层实现是由C/C++实现,如媒体,图形库等 java调用这样实现就需要用JNI(Java Native...

长平狐
2013/01/06
123
0
如何用thrift传送文件

这里有对thrift用的很熟的大牛吗?现在我用thrift在C++和java之间通讯,C++是客户端,java是服务器端。现在想要从C++客户端往Java服务器端传送文件,怎么处理啊?从Java服务器端忘C++客户端传...

liangxiao
2013/03/11
2.6K
1

没有更多内容

加载失败,请刷新页面

加载更多

从0搭建自己的webpack开发环境(五)

往期回顾: 从0搭建自己的webpack开发环境(一) 从0搭建自己的webpack开发环境(二) 从0搭建自己的webpack开发环境(三) 从0搭建自己的webpack开发环境(四) 前四篇文章我们已经掌握了w...

前端优选
23分钟前
4
0
docker 构建php-fpm 7.2(swoole) 镜像

mkdir -p ~/mnt/docker/phpmkdir -p ~/mnt/docker/php#下载swoole-2.2.0.tgz安装包到software 下载地址:http://pecl.php.net/package/swoole/2.2.0#创建Dockerfilevim ~/docker/......

Jack088
39分钟前
3
0
简单工厂

定义:由一个工厂对象决定创建出哪一种产品类的实例 类型:创建型,但不属于GOF23种设计模式 工厂类负责创建的对象比较少 客户端(应用层)只知道传入工厂类的参数,对于如何创建对象,不关心...

东风破2019
54分钟前
4
0
SSH安全加强两步走

从 OpenSSH 6.2 开始已经支持 SSH 多因素认证,本文就来讲讲如何在 OpenSSH 下启用该特性。 OpenSSH 6.2 以后的版本多了一个配置项 AuthenticationMethods。该配置项可以让 OpenSSH 同时指定...

Linux就该这么学
54分钟前
7
0
聊聊nacos的TcpSuperSenseProcessor

序 本文主要研究一下nacos的TcpSuperSenseProcessor TcpSuperSenseProcessor nacos-1.1.3/naming/src/main/java/com/alibaba/nacos/naming/healthcheck/TcpSuperSenseProcessor.java @Compon......

go4it
54分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部