Java 初学问题

[Richard14]

正在一边看书一边学 java ，学到集合的时候有两个问题：

1 、一般按照经验，hashmap 是使用频率最高的一种数据结构，大多数场景都能一把梭。java 中的 hashmap 内部实现是有序的吗？也就是如果我按顺序向 hashmap 添加 x,y,z ，能否保证后续遍历中也是按 xyz 的顺序获取？

2 、看书注意到 java 提供了很多相似的数据结构：Queue ，Stack ，Deque ，LinkedList 。功能各有限制，尤其是 queue 和 stack 把使用方式限定在很小的范围。逻辑上应该是被 deque 包含的，然后又被 LinkedList 包含，这是否意味着按照通常码农的使用经验倾向于用 LinkedList 表达所有，而不是专门为了特殊场景选一个功能非常有限的特殊数据类型？因为看起来比如如果使用 Queue 这个类万一需要获取列表长度都很麻烦

[taogen]

倾向于使用 Stack Overflow

[cmdOptionKana]

> 比如如果使用 Queue 这个类万一需要获取列表长度都很麻烦

大多数情况下，事先看需求，当认为需求很稳定时就可以使用这些数据结构，好处是逻辑更清晰。

[xingda920813]

1, 不能保证按插入顺序遍历，如有需要请使用 LinkedHashMap 。如果需要总是按照一个有比较器提供的排序来遍历，请使用 TreeMap 或 ConcurrentSkipListMap 。
2, Stack 跟 Vector 一样是过时的集合，不要使用，他们也并不线程安全，尤其是 iterator() 方法返回的迭代器需要手动同步，否则有可能抛出 CME 。LinkedList 是链表，如果要数组实现的 Stack 的话，现代 Java 里面可以使用 ArrayDeque 来代替 Stack 。关于数组实现和链表实现，他们各有相应的特点，并不是总是使用链表的。

[msg7086]

1. LinkedHashMap 。

2. 选用能满足功能的最小功能集的数据结构。当然如果你做个人项目或者敏捷开发的话，随便怎么用都行。

[Richard14]

@xingda920813
@msg7086
无序倒不至于功能就做不出来了，只是按照个人经验，如果 hashmap 有序，通常来讲可以避免一些麻烦。LinkedHashMap 看名字好像是底层用链表实现的？这是否意味着随机读写性能很糟糕。。

[luozic]

benchmark 和对应场景的合适选择语言和库。

Premature optimization is the root of all evil. 过早优化是万恶之源。—— Donald Knuth 高德纳

[thetbw]

ArrayList 解决所有，没有什么事一个循环解决不了的，如果有，那就两个

[Leviathann]

1. LinkedHashMap 内部额外维护了插入的顺序
2. LinkedList.java 的作者发推问过有没有人用过这个，他说这东西是他写的，但是自己从来没用过。如果要表示 stack 可以直接用 arrayDeque

[SeaTac]

问题 1 其实看看 hashmap 的实现就知道了
简单的说 hashmap 是对 key 生成 hashcode 然后放到一个 array 里面，这样能实现 o(1) put & o(1) get
对 key 生成 hashcode 是无法保证排序的
linkedhashmap 更像是一个 fifo cache ，理论上来说没有随机性能的问题

不太懂为什么要问问题 2 ，用 linkedlist 表达所有在我看来是一种滥用
不过 queue ，stack 在我接触过的生产代码里很少见到，倒不是因为用 linked list 表达所有，只是因为没有使用的必要

至于你说的 queue 的长度，queue 本身是一个 linkedlist ，是有 queue.size()的
stack 也有 size

[Richard14]

@seaiaddca 感谢大佬回复，很清晰了。那我感觉我如果写业务代码会优先选用 linkedhashmap 这个结构一把梭，我觉得大多数场景我不在意它与 hashmap 的细节上的优化性能差距。如果我的数据结构本身有顺序处理的需要的话，我可以避免自己维护另外一个顺序表

[book1925]

@Leviathann

很好奇为啥 LinkedList 没人用啊。现在也在看面试题说 List 在大量数据下用 ArrayList 的增删操作新能比 LinkedList 性能好很多。但是从原理来说链表增删节点的开销不应该比数组要小吗😂

[SeaTac]

@book1925
看情况，我自己遇到用 list 的绝大多数情况是 create list 和 iterate / get element ，很少很少对 list element 进行删除或者插入（除了创建 list ），这个情况下用 arraylist 是合理的

[SeaTac]

@Richard14
原则是根据具体需要选择数据结构
如果没有多线程的问题，在对 map 的插入顺序有要求的情况下用 linkedhashmap 是合理的

当然你可以写个 load test 试一试，不过我觉得没必要…

[FYFX]

@book1925 写 LinkedList 的作者以前在推特上问过，他也很好奇谁在用 java 的 LinkedList 反正他自己是没用过，就这条推特:https://twitter.com/joshbloch/status/583813919019573248

[Richard14]

@seaiaddca 大佬建议多线程环境下用啥呢

[SeaTac]

@Richard14
我只用过 concurrenthashmap ，没遇到过需要对 key order 有要求的 multi thread 场景，你可能得自己查一查

随便搜了一个： https://stackoverflow.com/questions/28653889/java-thread-safe-linkedhashmap-implementation

[Jooooooooo]

1. 7 及以前是"有序的", 意思是你每次遍历它顺序一样(当然是什么顺序只有遍历过后才知道). 8 以后就乱序了(防止有人写程序依赖这个顺序). map 的定义里没有要求顺序, 所以你应该认为它是无序的.

2. 很多基础的类就是为了实现而实现的, java 作者就坦言过, 他自己也从来没有用过 linkedList, 都是 arraylist 一把梭.

[Rocketer]

hasmap 顾名思义是用 hash 实现的，学数据结构时老师都会让学生自己实现一个 hash 表，就彻底明白为什么不可能有序了

[Dragonphy]

V 站最近多了很多无聊的提问，明明搜一下就行的
https://www.bing.com/search?q=hashmap+%E6%98%AF%E6%9C%89%E5%BA%8F%E7%9A%84%E5%90%97

[Morii]

打击下楼主的积极性，从我的角度看来

虽然你的提问一定程度上显示出你很「好学」很「认真」

但是这种学习方式感觉效率蛮低的

毕竟 google 一下或者 y2b 搜索下都能得到比楼上回复更易懂更详尽的回答（没有说楼上写的不好意思，只是随手写的很难比得上字字斟酌的文章 or 视频）

[SuperMild]

刚刚看 dev.java 看到关于 LinkedList 的说法：

- What was true for linked lists when computing was invented in the 60's does not hold anymore.
- The capacity of linked lists to outperform arrays on insertion and deletion operations is greatly diminished by modern hardware, CPU caches, and pointer chasing.

从数据结构上看，如果要在一个 list 中间插入元素、或删除元素，LinkedList 比 array 更高效。但由于硬件进步，这个差异已经变得非常小了。