### 1. 算法
在此输入正文
`反转链表` `冒泡排序` `二分查找(递归|非递归)` `另一道是在N个数中求前M大个数`
> * 一组排序数中,给定一个数,返回最接近且不大于这个数的位置
> * 把一个数组中奇数放前面,偶数放后面
> * 另一个是3亿条IP中,怎么找到次数出现最多的5000条IP
> * 一个大文件几个GB,怎么实现复制
### 3.LinkedHashMap
LinkedHashMap 维护着一个运行于所有条目的`双重链接列表`。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。
根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。
不过,我的建议是,大家首先首先需要记住的是:LinkedHashMap 能够做到按照`插入顺序或者访问顺序`进行迭代,这样在我们以后的开发中遇到相似的问题,才能想到用 LinkedHashMap 来解决,否则就算对其内部结构非常了解,不去使用也是没有什么用的。
主要记忆点:
> * JDK描述
differs is maintains a doubly-linked list TODO
> * 成员变量
extends HashMap
LinkedHashMap 采用的 hash 算法和 HashMap 相同,但是它重新定义了数组中保存的元素 Entry,该 Entry 除了保存当前对象的引用外,还保存了其上一个元素 before 和下一个元素 after 的引用,从而在哈希表的基础上又构成了双向链接列表。看源代码:
```
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* The iteration ordering method for this linked hash map: * <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder; # true访问顺序,false插入顺序
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head; # 双向链表头结点
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail; # 双向链表尾节点
```
> * 初始化
通过源代码可以看出,在 LinkedHashMap 的构造方法中,实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组,但额外可以增加 accessOrder 这个参数,如果不设置,默认为 false,代表按照插入顺序进行迭代;当然可以显式设置为 true,代表以访问顺序进行迭代。如:
```
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
```
我们已经知道 LinkedHashMap 的 Entry 元素继承 HashMap 的 Entry,提供了双向链表的功能。在上述 HashMap 的构造器中,最后会调用 init() 方法,进行相关的初始化,这个方法在 HashMap 的实现中并无意义,只是提供给子类实现相关的初始化调用。
但在 LinkedHashMap 重写了 init() 方法,在调用父类的构造方法完成构造后,进一步实现了对其元素 Entry 的初始化操作。
```
/**
* Called by superclass constructors and pseudoconstructors (clone,
* readObject) before any entries are inserted into the map. Initializes
* the chain.
*/
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
```
> * 存储
put:调用的还是父类hashMap的put方法。
get:先通过key的哈希值获取元素`e = getNode(hash(key) `如果accessOrder为true的话,执行`afterNodeAccess()`方法,然后返回e.value.
`afterNodeAccess()`的作用就是`move node to last`
afterNodeAccess代码如下:
```
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
```
*那么访问元素的时候如何做到按插入顺序还是访问顺序输出的呢?答案是遍历的时候用了map.entrySet().iterator(),而entrySet()又调用了LinkedEntryIterator,*
LinkedEntryIterator代码如下:
```
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
```
是返回了一个nextNode(),个nextNode()代码如下:
```
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
```
还有两个重要的方法
`afterNodeRemoval`、`afterNodeInsertion`
```
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
```
```
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
```
### 4. LinkedHashSet
`public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable `
只有六个方法
```
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
```
> * LinkedHashSet 是 Set 的一个具体实现,其维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序。
> * LinkedHashSet 继承与 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样,不过还是有一点点区别的(具体的区别大家可以自己去思考一下)。
> * 如果我们需要迭代的顺序为插入顺序或者访问顺序,那么 LinkedHashSet 是需要你首先考虑的。
### 4. hashSet
hashSet没有get方法,因为get方法没有意义。
hashSet的处理过程:调用hashMap的put方法,要插入的值做key,value是object对象。在hashMap中,当key不重复时,插入。重复时(hashCode()返回值相等,通过 equals 比较也返回 true)value覆盖旧值,key值不会有任何变化。返回null。hashSet利用这个实现去重功能。
### 5. CopyOnWriteArrayList
CopyOnWriteArrayList相当于线程安全的ArrayList,通过增加写时复制语义来实现线程安全性。底层也是通过一个可变数组来实现的。但是和ArrayList不同的时,它具有以下特性:
> * 它最适合于具有以下特征的应用程序:List 大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突
> * 支持高效率并发且是线程安全的
因为通常需要复制整个基础数组,所以可变操作(add()、set() 和 remove() 等等)的开销很大
> * 迭代器支持hasNext(), next()等不可变操作,但不支持可变 remove()等操作
> * 使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照
### 6. CopyOnWriteArraySet
它是线程安全的无序的集合,可以将它理解成线程安全的HashSet。有意思的是,CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet;但是,HashSet是通过“散列表(HashMap)”实现的,而CopyOnWriteArraySet则是通过“动态数组(CopyOnWriteArrayList)”实现的,并不是散列表。
和CopyOnWriteArrayList类似,CopyOnWriteArraySet具有以下特性:
1. 它最适合于具有以下特征的应用程序:Set 大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组,所以可变操作(add()、set() 和 remove() 等等)的开销很大。
4. 迭代器支持hasNext(), next()等不可变操作,但不支持可变 remove()等 操作。
5. 使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照。
近期热议
推荐标签 标签
-
SMTP
4 引用 • 18 回帖 • 589 关注
SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。
-
LaTeX
9 引用 • 32 回帖 • 169 关注
LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。
-
HBase
17 引用 • 6 回帖 • 44 关注
HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。
-
RYMCU
4 引用 • 6 回帖 • 38 关注
RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。
-
服务
41 引用 • 24 回帖 • 4 关注
提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。
-
Markdown
163 引用 • 1450 回帖 • 2 关注
Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。
-
反馈
123 引用 • 906 回帖 • 191 关注
Communication channel for makers and users.
-
H2
11 引用 • 54 回帖 • 641 关注
H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。
-
坑
69 引用 • 93 回帖
一些有用的避坑指南。
-
PWL
1 引用 • 487 回帖 • 7 关注
组织简介
用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖。
用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/用爱发电组织的核心驱动力:
- 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
- 自我保护:使用适当的 License 保护自己的原创作品。
- 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
- 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
- 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
- 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
- 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
-
生活
228 引用 • 1450 回帖
生活是指人类生存过程中的各项活动的总和,范畴较广,一般指为幸福的意义而存在。生活实际上是对人生的一种诠释。生活包括人类在社会中与自己息息相关的日常活动和心理影射。
-
Electron
15 引用 • 136 回帖 • 10 关注
Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。
-
Eclipse
75 引用 • 258 回帖 • 629 关注
Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。
- 链书
-
Java
3167 引用 • 8207 回帖
Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。
-
CSS
180 引用 • 447 回帖 • 2 关注
CSS(Cascading Style Sheet)“层叠样式表”是用于控制网页样式并允许将样式信息与网页内容分离的一种标记性语言。
-
倾城之链
23 引用 • 66 回帖 • 97 关注
-
CAP
11 引用 • 5 回帖 • 563 关注
CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。
-
Elasticsearch
116 引用 • 99 回帖 • 265 关注
Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。
-
Spring
940 引用 • 1458 回帖 • 156 关注
Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。
-
旅游
85 引用 • 895 回帖
希望你我能在旅途中找到人生的下一站。
-
星云链
3 引用 • 16 回帖 • 5 关注
星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网
-
心情
59 引用 • 369 回帖
心是产生任何想法的源泉,心本体会陷入到对自己本体不能理解的状态中,因为心能产生任何想法,不能分出对错,不能分出自己。
-
SQLite
4 引用 • 7 回帖 • 1 关注
SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。
-
CloudFoundry
5 引用 • 18 回帖 • 150 关注
Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。
-
WiFiDog
1 引用 • 7 回帖 • 547 关注
WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。
-
frp
15 引用 • 7 回帖 • 9 关注
frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于