同步操作将从 Java精选/Ebooks 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
同步集合与并发集合都为多线程和并发提供了合适的线程安全的集合,不过并发集合的可扩展性更高。
在Java1.5之前程序员们只有同步集合来用且在多线程并发的时候会导致争用,阻碍了系统的扩展性。Java5介绍了并发集合像ConcurrentHashMap,不仅提供线程安全还用锁分离和内部分区等现代技术提高了可扩展性。
集合类接口指定了一组叫做元素的对象。集合类接口的每一种具体的实现类都可以选择以它自己的方式对元素进行保存和排序。有的集合类允许重复的键,有些不允许。
Java集合类提供了一套设计良好的支持对一组对象进行操作的接口和类。Java集合类里面最基本的接口有:
Collection:代表一组对象,每一个对象都是它的子元素。
Set:不包含重复元素的Collection。
List:有顺序的collection,并且可以包含重复元素。
Map:可以把键(key)映射到值(value)的对象,键不能重复。
解题思路:
1、首先将给定的url调用hash方法计算出对应的hash的value,在10亿的url中相同url必然有着相同的value。
2、将文件的hash table放到第value%n台机器上。
3、value/n是机器上hash table的值。
将文件分布在多个机器上,这样要处理网路延时。假设有n台机器。
首先hash文件得到hash value v 将文件的hash table 放到第v%n 台机器上。 v/n是机器上hash table的值。
问题分析:
将文件的url进行hash,得到值value,相同的url的文件具有相同的value,所以会被分配到同一台机器v%n上。在同一台机器上的重复的url文件具有相同的value/n值,如果出现了冲突,不同的url在同一台机器上也可能有相同的value/n值。在每个机器上将value/n值作为key,url值作为value构成hash表进行去重。最后将内存中去重后的hash表中的value值即url写入磁盘。合并磁盘中的各部分url文件,完成去重。
每个url地址大小为 56byte;
服务器内容大小为 4G =4*1024=4096kb=4096*1024 byte;
JDK1.8之前,其数据结构为数组加链表。JDK1.8之后的优化,其数据结构变成了数组+链表+红黑树
当链表上的结点过多时,查询一个结点,在JDK1.8之前,需要遍历整个节点,效率为O(n)。而在JDK1.8中,如果结点达到阈值TREEIFY_THRESHOLD(默认为8)时,会将链表结构转成红黑树结构,这样再查询时,如果数组的first结点是树结构,则采用树的查询算法,效率为O(logn),否则还是遍历链表。参见JDK1.8源码
当树上结点过多时,阈值为UNTREEIFY_THRESHOLD(默认为6),会进行树转链表操作。至于为什么不是8,是为了防止平凡的进行树--链表的转换。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 第一个结点为红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 否则遍历链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2、JDK1.8之前,ConcurrentHashMap通过将整个Map划分成N(默认16个)个Segment,而Segment继承自ReentrantLock ,通过对每个Segment加锁来实现线程安全。而在JDK1.8后,摒弃了这种实现方式,采用了CAS + Synchronized,对链表头结点进行加锁,来实现线程安全。参考JDK1.8源码
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 此处f即为链表的头结点
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
public class Test {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer integer = iterator.next();
if(integer==2)
list.remove(integer);
}
}
}
执行上段代码是有问题的,会抛出ConcurrentModificationException异常。
原因分析:调用list.remove()方法,导致modCount和expectedModCount的值不一致。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
解决办法:在迭代器中如果要删除元素的话,需要调用Iterator类的remove方法。
public class Test {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer integer = iterator.next();
if(integer==2)
iterator.remove(); //注意这个地方
}
}
}
假设给定一个链表,删除链表中倒数第n个节点,并且返回链表的头节点。
实例:
给定一个链表: 1->2->3->4->5,和n=2。
当删除倒数第二个节点后,链表变为1->2->3->5。
分析:表明给定的n节点是有效的。
解题思路:
1、删除的节点可以通过双指针pre和index;
2、双指针开始都是指向头节点,index先走到比头节点大n的位置;
3、两个指针同时往后遍历,当index的下一个为空时,此时pre指向的就是需要删除的那一个节点;
4、删除这个节点还需要分析后续节点是否为空;
5、如果后续不为空需要后面的节点覆盖它,若为空,就只需要设置为null。
实现代码如下:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(null == head){
return null;
}
if(n <= 0){
return head;
}
ListNode pre = head;
ListNode index = head;
ListNode orghead = head;
for(int i = 1;i < n ;i++){ //让i先走n步
index = index.next;
if(null == index){
return null;
}
}
while(null != index.next){ //到n的位置,pre开始遍历
orghead = pre;
pre = pre.next;
index = index.next;
}
//删除时得考虑删除节点是否有后续节点
if(null != pre.next){
pre.val = pre.next.val; //有就往前移
pre.next = pre.next.next;
}else{
if(null == pre.next){ //没有后续,需把它设置为null值
return null;
}
orghead.next = null;
}
return head;
}
}
Java集合类是一种非常实用的工具类,主要用于保存、盛装其它数据(集合里只能保存对象),因此集合类也被成为容器类。
所有的集合类都位于java.util包下,在java.util.concurrent下还提供了一些支持多线程的集合类。
Java的集合类主要由两个接口派生而来:Collection和Map,这两个是Java集合框架的根接口。
Collection接口
Collection派生出三个子接口,Set代表不可重复的无序集合、List代表可重复的有序集合、Queue是java提供的队列实现;Collection是最基本的集合接口,它提供了一些通用的方法,供子接口调用。
Map接口
Map实现类都用于保存具有映射关系的数据,它们保存的数据都是key-value对,如果要查找Map中的数据,总是根据key来获取,所以key是不可重复的,它用于标识集合里的每项数据。
ArrayList的底层是数组实现且数组的默认值是10,如果插入10000条要不断的扩容,耗费时间,所以我们调用ArrayList的指定容量的构造器方法ArrayList(int size) 就可以实现不扩容,就提高了性能。
可以使用Collections包下的unmodifiableMap()方法,通过这个方法返回的map是不可以修改的。这样改变集合的任何操作都会抛出Java.lang.UnsupportedOperationException异常。
Collections包也提供了对list和set集合的方法。
Collections.unmodifiableList(List)
Collections.unmodifiableSet(Set)
也可以使用Collections.unmodifiableCollection(Collection c)方法来创建一个只读集合,这样改变集合的任何操作都会抛出Java.lang.UnsupportedOperationException异常。
示例代码:
List<String> list = new ArrayList<>();
list. add("微信公众号");
Collection<String> unmlist = Collections.unmodifiableCollection(list);
unmlist.add("Java精选"); // 运行时此行报错
System.out.println(list.size());
遍历集合的时可以使用并发集合类来避免ConcurrentModificationException异常。
例如使用CopyOnWriteArrayList集合,而不是ArrayList集合。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。