### 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. 使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照。
近期热议
推荐标签 标签
-
Sublime
10 引用 • 5 回帖
Sublime Text 是一款可以用来写代码、写文章的文本编辑器。支持代码高亮、自动完成,还支持通过插件进行扩展。
-
Markdown
163 引用 • 1450 回帖
Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。
-
Linux
915 引用 • 931 回帖
Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 Unix 的多用户、多任务、支持多线程和多 CPU 的操作系统。它能运行主要的 Unix 工具软件、应用程序和网络协议,并支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心的设计思想,是一个性能稳定的多用户网络操作系统。
-
支付宝
29 引用 • 347 回帖
支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。
-
DevOps
40 引用 • 24 回帖
DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。
-
反馈
123 引用 • 906 回帖 • 192 关注
Communication channel for makers and users.
-
SQLite
4 引用 • 7 回帖 • 2 关注
SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。
-
PostgreSQL
22 引用 • 22 回帖
PostgreSQL 是一款功能强大的企业级数据库系统,在 BSD 开源许可证下发布。
-
Tomcat
162 引用 • 529 回帖 • 4 关注
Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。
-
InfluxDB
2 引用 • 56 关注
InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。
-
CAP
11 引用 • 5 回帖 • 563 关注
CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。
-
jsoup
6 引用 • 1 回帖 • 462 关注
jsoup 是一款 Java 的 HTML 解析器,可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API,可通过 DOM,CSS 以及类似于 jQuery 的操作方法来取出和操作数据。
-
Flume
9 引用 • 6 回帖 • 594 关注
Flume 是一套分布式的、可靠的,可用于有效地收集、聚合和搬运大量日志数据的服务架构。
-
Postman
4 引用 • 3 回帖
Postman 是一款简单好用的 HTTP API 调试工具。
-
C
83 引用 • 165 回帖 • 43 关注
C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。
-
服务器
124 引用 • 580 回帖
服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。
-
Hadoop
82 引用 • 122 回帖 • 621 关注
Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。
-
阿里云
89 引用 • 345 回帖
阿里云是阿里巴巴集团旗下公司,是全球领先的云计算及人工智能科技公司。提供云服务器、云数据库、云安全等云计算服务,以及大数据、人工智能服务、精准定制基于场景的行业解决方案。
-
Sym
523 引用 • 4581 回帖 • 690 关注
-
设计模式
198 引用 • 120 回帖 • 1 关注
设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。
-
DNSPod
6 引用 • 26 回帖 • 521 关注
DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。
-
BAE
19 引用 • 75 回帖 • 618 关注
百度应用引擎(Baidu App Engine)提供了 PHP、Java、Python 的执行环境,以及云存储、消息服务、云数据库等全面的云服务。它可以让开发者实现自动地部署和管理应用,并且提供动态扩容和负载均衡的运行环境,让开发者不用考虑高成本的运维工作,只需专注于业务逻辑,大大降低了开发者学习和迁移的成本。
-
脑图
21 引用 • 58 回帖 • 1 关注
脑图又叫思维导图,是表达发散性思维的有效图形思维工具 ,它简单却又很有效,是一种实用性的思维工具。
-
JVM
180 引用 • 120 回帖 • 2 关注
JVM(Java Virtual Machine)Java 虚拟机是一个微型操作系统,有自己的硬件构架体系,还有相应的指令系统。能够识别 Java 独特的 .class 文件(字节码),能够将这些文件中的信息读取出来,使得 Java 程序只需要生成 Java 虚拟机上的字节码后就能在不同操作系统平台上进行运行。
-
Bootstrap
18 引用 • 33 回帖 • 683 关注
Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发,是一个 CSS / HTML 框架。
-
职场
126 引用 • 1699 回帖
找到自己的位置,萌新烦恼少。
-
RIP
8 引用 • 92 回帖 • 291 关注
愿逝者安息!
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于