hashMap、List 和 Set 的数据结构
任何人都可以指导我深入了解所使用的数据结构以及它是如何在 Util Collection 页面的列表、集合和映射中实现的。
在面试中,大多数问题都是关于算法的,但我从未在任何地方看到过实现细节,有人可以分享一下信息吗?
Can any one please guide me to look in depth about the Data Structures used and how is it implemented in the List, Set and Maps of Util Collection page.
In Interviews most of the questions will be on the Algorithms, but I never saw anywhere the implementation details, Can any one please share the information.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
要了解 Java 如何实现集合,最好的地方就是免费提供的源代码本身。通常,列表被实现为数组(ArrayList)或链接列表(LinkedList);集合可以是哈希表(HashSet)或树(TreeSet);映射是哈希表(HashMap)。
操作数组、链表、哈希表和二叉树或 n 叉树(添加、删除、搜索、排序)的算法本身就足够复杂,需要一门完整的课程来涵盖所有这些算法。任何自己进行程序设计的人通常都需要牢记这些算法及其性能权衡。教科书学习和/或练习是无可替代的。
To learn how Java implements collections, the definitive place to go is the source code itself, freely available. Generally, Lists are implemented as either arrays (ArrayList) or linked lists (LinkedList); sets are either hashtables (HashSet) or trees (TreeSet); and maps are hashtables (HashMap).
Algorithms for manipulating arrays, linked lists, hashtables, and binary or n-ary trees (add, remove, search, sort) are complex enough in themselves that an entire course is necessary to cover them all. Anyone doing their own program design typically needs to understand these algorithms and their performance tradeoffs by heart. There's no substitute here for textbook study and/or practice.
API 的源代码可用,获取 JDK 并从安装文件夹中打开 src.zip 文件。
The source code of the API is available, get a JDK and open up the src.zip file from the installation folder.
ArrayList:数组
LinkedList:双向链表(Entry 对象)
HashMap:Entry 对象数组,每个 Entry 都指向单向链表
HashSet :内部使用HashMap,将数据存储为Key,将虚拟对象(Object类)存储为Map中的Value。
TreeMap:Entry 对象的红黑树实现。
TreeSet:内部使用TreeMap。键作为数据,虚拟对象作为值。
*Entry:是这些集合中的内部类,通常具有Key、Value、其他Entry对象的引用等。
ArrayList: array
LinkedList: doubly linked list (Entry objects)
HashMap: array of Entry objects each Entry pointing to singly linked list
HashSet: internally uses HashMap, stores data as Key and dummy Object (of class Object) as Value in the map.
TreeMap: Red-Black tree implementation of Entry objects.
TreeSet: internally uses TreeMap. Key as data and dummy object as value.
*Entry: is an internal class in these collections and generally has Key, Value, references for other Entry objects etc.
您始终可以打开源文件,它都在那里,但是,我不会推荐它,因为通常它们很难理解。相反,我会尝试找到底层数据结构并进行查找。维基百科包含您想了解的有关这些主题的大部分信息,而谷歌则包含绝对的其余信息。
列表只是一个动态数组,
集合是一个... 集合,
映射通常是哈希表,以键的哈希为键,并存储为键值对。
如果您要深入研究源代码,我建议您熟悉“它可能是如何工作的”,否则它将很难理解,尤其是哈希表。
You can always open the source files, it's all there, however, I wouldn't recommend it as usually they are quite hard to understand. Instead, I'd try finding the underlying data structure, and looking it up. Wikipedia contains most of the information you want to know on these subjects, and google contains the absolute rest.
List is just a dynamic array,
Set is a... set,
And maps are usually hash tables keyed by the key's hash, and stored as key-value pair.
If you're going to dive into the source code, I'd recommend familiarizing yourself with "how-it-probably-works", cause otherwise it will be hard to understand, especially the hash table.