Fork me on GitHub
image frame

Java Interface SortedMap

Java Interface SortedMap

extends Map

方法

就只有这几个方法,然后就没有内容了

  • Comparator<? super K> comparator();
  • SortedMap<K,V> subMap(K fromKey,K toKey);
  • SortedMap<K,V> headMap(K toKey);
  • SortedMap<K,V> tailMap(K fromKey);
  • K firstKey();
  • K lastKey();
  • Set keySet();
  • Collection values();
  • Set<Map.Entry<K,V>> entrySet();

Java abstract class AbstractMap<K,V>

Java AbstractMap

介绍了AbstractMap内的方法和静态方法的实现,内部还有两个静态内部类SImpleEntry,SimpleImmutableEntry暂时不讨论

##构造方法

空的构造方法,

size

通过entrySet获取一个Set<Map.Entry<K,V>>,然后调用Set的size方法

isEmpty

调用size(), 看看size是否为零

containsKey

调用entrySet() 获取Set,调用Set.iterator()获取一个迭代器,使用这个迭代器进行遍历查询
需要注意的是,在方法内部使用了if语句,通过Object key是否为空来确定使用 == null 还是 equals 来进行判断是否匹配

containsValue

同上

get

同上,只不过匹配到了对应的key之后使用Entry.getValue来取出value

put

未实现

remove

同样使用迭代器获取到正确的键值对Entry。
然后如果Entry的值不为空,则调用迭代器的remove把该键值对去掉,
然后返回value

putAll

for循环遍历传入的参数map.entrySet(),然后put(key,value)

clear

调用entrySet().clear()

Set keySet

transient

Collecion values;

transient

keySet()

获取keySet,
如果keySet为空,则new一个AbstractSet{
iterator <-> entrySet.iterator()

size <-> AbstractMap.this.size()
isEmpty<-> AbstractMap.this.isEmpty()
clear <-> AbstractMap.this.clear()
contains <-> AbstractMap.this.containsKey()
}
返回Set

values

原理同上
返回Collection

entrySet

abstract

equals

如果o == this 返回true
如果类型不是Map ,返回false
强制类型转换Object o 为Map o
如果size结果不一致,返回false
迭代器遍历this.entrySet().iterator();
只要o内包含this内所有键值对且一致,则相等
(看代码的话好像不考虑o内部有更多的数据)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
try {
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}

hashCode

迭代器遍历,返回值为所有Entry的hashCode的返回值

toString

没仔细看

clone

throws CloneNotSupportedException
super.clone(),
然后把结果的keySet和values设为null
然后返回

静态方法

eq

现根据是否都为null判断,再调用equals

静态内部类

SimpleEntry

SimpleImmutableEntry

Java Interface Map

Java Interface Map

Map

Map.java内部可以分成4个部分

  • 逻辑上Map接口需要实现的方法
  • 作为数据结构应该实现的方法
  • 默认实现的方法
  • Map.Entry

逻辑上Map接口需要实现的方法

  • size 大小
  • isEmpty 是否为空
  • containsKey 是否包含有某个键
  • containsValue 是否包含有某个值
  • get 取
  • put 放
  • remove 移除
  • putAll 全部放
  • clear 清楚
  • Set keySet 获取所有键
  • Collection values 获取所有值
  • Set<Map.Entry<K,V>> entrySet 获取所有entry

作为数据结构应该实现的方法

  • boolean equals(Object o)
  • int hashCode

默认方法

  • getOrDefault 从一个键获取一个值,如果没有值,则默认返回
    • 先get ,如果没有就返回默认值,有则返回get到的值
  • forEach 遍历一个map,
    • 用到了BiConsumer
    • 先判断遍历执行的action是否为空,然后通过entrySet获取键值对,然后从键值对拿到key和value,传给action
  • replaceAll
    • 用了BiFunction
    • 遍历一遍entrySet()然后将取到的key,value作为参数给function.apply之后,将结果赋值给value,然后最后entry.setValue
  • putIfAbsent 如果对应的key的value是空的话,就赋值,否则不赋值
  • remove 移除
    • 如果 传入的value和通过key取得的value不一致 则 返回 false, 不移除
    • 如果 通过key取得的value为空,同时map内部不包含该key,也返回false不移除
    • 其他情况 remove(key) ,return true
  • replace 三个参数
    • 同上,remove改为put(key,newValue)
  • replace 两个参数
    • 只要通过key获取到的value不为空或者key在目标map中存在,就可以将传入的value替换到对应的key中
  • computeIfAbsent 如果key对应的value == null, 则对key做处理后 的结果作为value传入
    • 如果 value!= null 或者function的结果==null,则不改变,并返回value
    • 返回的value有可能为空
  • computeIfPresent 如果key对应的value不为空,则处理并将结果传入,其他同上
  • compute 不讲道理,直接将key处理一遍,然后传入到value
  • merge
    • 如果key中已有值,则对oldvalue与newvalue一起处理,然后返回值作为newvalue,否则将传入的value作为newvalue
    • 如果最终newvalue为空,则移除key,否则将newvalue作为新的value传入

Map.Entry

Map.Entry是一个键值对,有简单的

  • getKey
  • getValue
  • setValue
  • equals
  • hashCode
    这些方法,已经内部已经实现了静态的比较方法。
  • comparingByKey 以自然顺序比较
  • comparingByValue 以自然顺序比较
  • comparingByKey 自定义Comparator
  • comparingByValue 自定义 Comparator

source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
public Interface Map<K,V>{
int size();

boolean isEmpty();

boolean constainsKey(Object key);

boolean containsValue(Object value);

V get(Object key);

V put(Object key,Object value);

V remove(Object key);

void putAll(Map<? extends K, ? extends V> m);

void clear();

Set<K> keySet();

Collection<V> values();

Set<Map.Entry<K,V>> entrySet();

Interface Entry<K,V> {
K getKey();

V getValue();

V setValue(V value);

boolean equals(Object o);

int hashCode();

public static <K extends Comparable<? super K> ,V> Comparator<Map.Entry<K,V> comparingByKey(){
return (Comparator<Map.Entry<K,V>> & Serializable) (c1,c2)->c1.getKey().compareTo(c2.getKey());
}

public static <K,V extends Comparable <? super V>> Comparator<Map.Entry<K,V>> comparingByValue(){
return (Comparator<Map.Entry<K,V>> & Serializable) (c1,c2) -> c1.getValue().compareTo(c2.getValue());
}

public static <K,V> Comparator<Map.Entry<K,V>> comparingByKey(Comparator<? super K> cmp){
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K,V>> & Serializable)(c1,c2) -> cmp.compare(c1.getKey(),c2.getKey());
}

public static <K,V> Comparator<Map.Entry<K,V>> comparingByValue(Comparator<? super V> cmp){
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K,V>> & Serializable)(c1,c2)->cmp.compare(c1.getValue(), c2.getValue());
}
}

boolean equals (Object o);

int hashCode();

default V getOrDefault(Object key , V defaultValue){
V v;
return (((v = get(key)) != null) || constainsKey(key))
? v
: defaultValue;
}

default void forEach(BiConsumer<? super K, ? super V> action){
Objects.requireNonNull(action);
for(Map.Entry<K,V> entry :entrySet()){
K k;
V v;
try{
k = entry.getKey();
v = entry.getValue();
} catch (IllegalStateException ise){
throw new ConcurrentModificationException(ise);
}

action.accept(k,v);
}
}

default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function){
Objects.requireNonNull(function);
for(Map.Entry<K,V> entry : entrySet()){
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch (IllegalStateException ise){
throw new ConcurrentModificationException(ise);
}

v = function.apply(k,v);

try{
entry.setValue(v);
} catch(IllegalStateException ise){
throw new ConcurrentModificationException(ise);
}
}
}

default V putIfAbsent(K key, V value){
V v = get(key);
if( v== null){
v = put(key,value);
}

return v;
}

default boolean remove(Object key,Object value){
Object vurValue = get(key);
if(!Objects.equals(curValue ,value) ||
(curValue == null && !constainsKey(key)){
return false;
}
remove(key);
return true;
}

default boolean replace(K key,V oldValue, V newValue){
Object curValue = get(key);
if( !Objects.equals(curValue,oldValue) ||
(curValue == null && !containsKey(key))){
return false;
}

put(key,newValue);
return true;
}

default V replace(K key, V value){
V curValue;
if(((curValue = get(key)) != null) || containsKey(key)){
curValue = put(key,value);
}
return curValue
}

default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction){
Objects.requireNonNull(mappingFunction);
V v;
if((v = get(key)) == null ){
V newValue
if((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}

return v;
}

default V computeIfPresent(K key,
BiFunction<? super K , ? super V, ? extends V> remappingFunction){
V oldValue;
if((oldValue = get(key)) != null){
V newValue = remappingFunction.apply(key,oldValue);
if(newValue != null){
put(key,newValue);
return newValue;
} else {
remove(key);
return null;
}
}
}

default V compute(K key,BiFunction<? super K, ? super V , ? extends V> remappingFunction){
Objects.requireNonNull(remappingFunction);

V newValue = remappingFunction.apply(key,oldValue);
if(newValue == null){
if(oldValue != null || containsKey(key)){
remove(key);
return null;
} else {
return null;
}
} else {
put(key,newValue);
return newValue;
}
}

default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction){
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);

V oldValue = get(key);
V newValue = (oldValue == null ?) value : remappingFunction.apply(oldValue,value);

if(newValue == null){
remove(key);
} else {
put(key,newValue);
}

return newValue;
}
}

4.2.1 信道的容量定义

4

4.2

4.2.1 信道容量定义

(2) 信道的信息传输率

  • 如果信源商为H(X),希望在信道输出端接收的信息量就是X(X),由于干扰的存在,一般只能接收到I(X:Y).
  • 输出端Y往往只能获得关于输入x的部分信息,这是由于平均互信息性质决定的:I(X:Y) <= H(X)
  • I(X:Y) 是

(3)信道容量

  • 信道容量C,
  • 单位时间的信道容量C_t^2

(4)结论

  • C与C_t

4.2.2 几种特殊离散信道的信道容量

离散无噪信道信道容量

  • 具有一一对应关系的信道(无损信道)

    • 信道矩阵
      • 对应关系
        • 已知X后,Y没有不确定性
      • C = maxI(X:Y)= maxH(x)=log_2 n (bit/符号)
  • 具有扩展性性能的信道

  • 具有归并性能的无噪信道

    • n>m,输入x的符号集个数大于输出y的符号集个数

Java LinkedList

Java LinkedList

LinkedList内部有3个transient 变量 分别是

1
2
3
transient int size = 0;
transient Node<E> first;
transient Node<E> last;

想来first与last应该就是头尾结点了.

LinkedList.Node

Node 是一个静态内部类,保存了前后结点和本身的item的信息

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>. Deque<E>, Cloneable, java.io.Serializable{

private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;

Node(Node<E> pre,E element,Node<E> next){
this.item = element;
this.next = next;
this.prev = pre;
}
}
}

Java Deque

Java Deque

Deque 双端队列,内部有双端队列的相关方法,同时也有Stack,Queue和Colleciton的相关操作方法.

Deque内部有两个迭代器,一个是递减迭代器.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public Deque<E> extends Queue<E>{
void addFirst();
void addLast();
boolean offerFirst();
boolean offerLast();
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getLast();
E peekFirst();
E peekLast();

boolean removeFirstOccurence(Object o);
boolean removeLastOccurence(Object o);

// Queue Methods
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();

// Stack Methods
void push(E e);
E pop();


// Collection Methods
boolean remove(Object o);
boolean contains(Object o);
public int size();

Iterator<E> iterator();

Iterator<E> descendingIterator();

}

Java AbstractSequentialList

Java AbstractSequentialList

这次源码比较短2333

可以看到,在AbstractSequentialList中实现了AbstractList中的抽象方法get和抛出UnsupportedOperationException的方法set,add,remove.

同时这些方法都通过listIterator()返回的迭代器实现,但是在AbstractSequentialList中的listIterator()是一个抽象方法,并没有实现.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public abstract class AbstractSequentialList<E> extends AbstractList<E>{
protected AbstractSequentialList{

}

public E get(int index){
try{
return listIterator(index).next();
} catch(NuSuchElementException exc){
throw new IndexOutOfBoundsException("index: "+index);
}
}

public E set(int index, E element){
try{
ListIterator<E> e =listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch(NoSuchElementException exc){
throw new IndexOutOfBoundsException("index : "+index);
}
}

public void add(int index, E element ){
try{
listIterator(index).add(element);
} catch(NoSuchElementException exc){
throw new IndexOutOfBoundsException("index: "+index);
}
}

public E remove(int index){
try{
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch(NoSuchElementException exc){
throw new IndexOutOfBoundsException("index: "+index);
}
}

public boolean addAll(int index, Collection<? extends E> c){
try{
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
Iterator<? extends E> e2 = c.Iterator();
while( e2.hasNext()){
e1.add(e2.next());
modified = true;
}
return modified;
} catch(NoSuchElementException exc){
throw new IndexOutOfBoundsException("index : "+index);
}
}

public Iterator<E> iterator(){return listIterator();}

public abstract ListIterator<E> listIterator(int index);
}

Java Queue

Java Queue

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
public interface Queue<E> extends Collection<E>{
boolean add(E e);

boolean offer(E e);

E remove();

E poll();

E element();

E peek();
}

分析

Queue 定义了一些队列操作所需要的方法

  • 插入操作
    • add
    • offer
  • 取出并去除操作
    • remove
    • poll
  • 取出不删除操作
    • element
    • peek

每个操作的不同方法基本上就是是否会抛出异常的区别

Java ArrayList

Java ArrayList

介绍

ArrayList 内部维护了一个

1
transient Object[] elementData;

调用构造函数的时候把内部的静态空数组赋值给elementData.或者根据长度赋值一个新的数组

add,get等操作通过调用elementData来实现, 如果elementData的长度不足,则经过一连串跳转之后调用native方法将数组复制到一个size比原先大1的新数组中.

ArrayList

1
2
3
ArrayList<E> extends AbstractList<E> implements List<E> ,RandomAccess,Cloneable,java.io.Serializable{
...
}

ArrayList类实现了4个interface

  • List
  • RandomAccess
  • Cloneable
  • java.io.Serializable

除了List接口之外,其余的三个接口都是空的

1
2
3
4
5
6
7
8
9
10
public interface RandomAccess{

}

public interface Cloneable{

}

public interface Serializable {
}

RandomAccess

表示实现了该接口的类使用for循环迭代比使用迭代器更快

Cloneable

实现了该接口的类就需要重写Object.clone()方法

API原文为:

By convention, classes that implement this interface should override
Object.clone (which is protected) with a public method.

Serializable

表示该类可序列化,需要自定义一个序列号的uid作为识别

1
private static final long serialVersionUID = 8683452581122892189L;
  • © 2020 Kfdykme
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信