java cookbook pdf_Java Cookbook之基本数据结构笔记

一时失言乱红尘 2022-11-06 04:54 86阅读 0赞

写函数写特征不会Java太太太蛋疼.....

The Collection Framework

List,Set,Map和Queue是Collections框架下的四个基本的数据结构。List和Set是序列型的(一个有序，一个无需)。Map是一个键值对存储。Queue是栈式的存储。

下面是各个Interfaces对应的Implementataions.Interfaces和Implementations关系的一些解答：

In the Java programming language, an interface is a reference type, similar to a class, that can contain onlyconstants, method signatures, default methods, static methods, and nested types. Method bodies exist only for default methods and static methods. Interfaces cannot be instantiated—they can only be implemented by classes or extended by other interfaces.>

What it's useful for

One of its uses is for it to be used as a face for a service. When two parties work together to form a service-requester & service-provider kind of relationship, the service provider provides the face of the service (as to what the service looks like) in the form of an interface.

One of the OOP concept is "Abstraction" which means to hide away complex working of the systems and show only what is necessary to understand the system. This helps in visualizing the working of a complex system. This can be achieved throughinterfacewhere in each module is visualized (and also implemented) to work through interface of another moduleImplements vs extends: When to use? What's the difference?stackoverflow.com![2b169c55ec5abe563f206c84cb22932f.png][]What is the difference between an interface and abstract class?stackoverflow.com![2b169c55ec5abe563f206c84cb22932f.png][]What is an interface in Java?stackoverflow.com![2b169c55ec5abe563f206c84cb22932f.png][]

这些数据结构之间的关系：

在进入Collections之前可以先复习下正常list的一些操作

import java.util.Arrays;

class arrayBasic\{

// find the biggestpublic static int findBiggest(int\[\] list)\{

int max = list\[0\];

for (int i = 1; i < list.length;i++)\{

if (list\[i\] > max) max = list\[i\];

return max;

// find the averagepublic static double findAverage(int\[\] list)\{

int len = list.length;

double sum = 0.0;

for (int i:list)\{

sum =+ i;

double result = sum/len;

return result;

// copy the arraypublic static int\[\] copyArray(int\[\] list)\{

int len = list.length;

int\[\] res = new int\[len\];

for(int i=0;i

res\[i\] = list\[i\];

return res;

// flip the array aroundpublic static int\[\] flipArray(int\[\] list)\{

int len = list.length;

for (int i=0;i

int tmp = list\[i\];

list\[i\] = list\[len-1-i\];

list\[len-1-i\] = tmp;

return list;

public static void main(String args\[\])\{

int\[\] demo = \{5,3,2,1,4,55\};

System.out.println(Arrays.toString(demo));

int res = findBiggest(demo);

double avg = findAverage(demo);

int\[\] demo2 = copyArray(demo);

System.out.println(Arrays.toString(demo2));

System.out.println(res);

System.out.println(avg);

int\[\] demo3 = flipArray(demo);

System.out.println(Arrays.toString(demo3));

ArrayList

ArrayList是java.util中的标准库。它封装了array的功能但是允许自动进行扩展(默认的int\[\]在生成的同时必须也声明数组大小)

但是由于ArraryList是一个class所以没办法直接使用Java的列表语法去访问。ArrayList包含了add,retrieve,find以及size等一系列方法(以及在下一次扩展内存占用空间前可以塞进多少数据)。

声明一个ArrayList的方法如下: 可以防止不合法的类型没有办法被放入你刚刚创建的列表

List myList = new ArrayList<>();

声明变量时使用接口类List是一个不错的习惯，尽管你是在创建一个ArrayList对象。这会使得在List的实现之间切换更方便。

<>代表你需要copy在声明变量的时候一直的变量类型。<>也叫做diamond operator。

在Java13中，我们可以进一步简化声明语句：

var myList = new ArrayList();

下面是大部分在List接口中定义的方法。在ArrayList以及其他List的实现中都有存在。

只得提一下toArray()这个转换方法，可以把提供给这个方法的内容转变为一个List

List.of和Arrays.asList的区别https://stackoverflow.com/questions/46579074/what-is-the-difference-between-list-of-and-arrays-asliststackoverflow.com

在Class中使用泛型

我们可以在定义类时候使用来解决这个问题

下面就是一个简单的使用泛型来实现Stack的例子。每次调用push,pop方法的时候，T就会作为参数类型被传递。

public class MyStack implements SimpleStack \{

private int depth = 0;

public static final int DEFAULT\_INITIAL = 10;

private T\[\] stack;

public MyStack() \{

this(DEFAULT\_INITIAL);

public MyStack(int howBig) \{

if (howBig <= 0) \{

throw new IllegalArgumentException(

howBig + " must be positive, but was " + howBig);

stack = (T\[\])new Object\[howBig\];

@Override

public boolean empty() \{

return depth == 0;

/\*\* push - add an element onto the stack \*/

@Override

public void push(T obj) \{

// Could check capacity and expand stack\[depth++\] = obj;

/\* pop - return and remove the top element \*/

@Override

public T pop() \{

\--depth;

T tmp = stack\[depth\];

stack\[depth\] = null;

return tmp;

/\*\* peek - return the top element but don't remove it \*/

@Override

public T peek() \{

if (depth == 0) \{

return null;

return stack\[depth-1\];

public boolean hasNext() \{

return depth > 0;

public boolean hasRoom() \{

return depth < stack.length;

public int getStackDepth() \{

return depth;

每次在创建类实例 的时候，对应的类型会被绑定

MyStack theAccounts = new MyStack<>( );

如果我们在创建的时候不声明类型，那么java会作为java.lang.Object类处理。那么在getter方法的时候就会需要做downcast. 下面可以看个例子。第一次调用的时候简单String，第二次调用的时候第三次downcast会失败，因为塞尔两个java.util.Date的类型.

public class MyStackDemo \{

@SuppressWarnings(\{"rawtypes","unchecked"\})

public static void main(String\[\] args) \{

MyStack ms1 = new MyStack<>();

ms1.push("billg");

ms1.push("scottm");

while (ms1.hasNext()) \{

String name = ms1.pop();

System.out.println(name);

// Old way of using Collections: not type safe. // DO NOT GENERICIZE THIS MyStack ms2 = new MyStack();

ms2.push("billg"); // EXPECT WARNING ms2.push("scottm"); // EXPECT WARNING ms2.push(new java.util.Date()); // EXPECT WARNING

// Show that it is broken try \{

String bad = (String)ms2.pop();

System.err.println("Didn't get expected exception, popped " + bad);

\} catch (ClassCastException ex) \{

System.out.println("Did get expected exception.");

// Removed the brokenness, print rest of it. while (ms2.hasNext()) \{

String name = (String)ms2.pop();

System.out.println(name);

遍历结构化数据的方法

Java提供的非常多遍历的方法：Stream.forEach() method (Java 8)

Iterable.forEach() method (Java 8)

Java “foreach” loop (Java 5)

java.util.Iterator (Java 2)

Three-part for loop

while loop \* Enumeration

下面来说一说每一种方法：

STREAM.FOREACH METHOD (JAVA 8)

Stream是java函数式编程的遍历方法。下面是个例子：

$ jshell

jshell> import java.io.\*;

jshell> BufferedReader is =

new BufferedReader(new FileReader("/home/ian/.profile"));

is ==> java.io.BufferedReader@58651fd0

jshell> is.lines().forEach(System.out::println)

... prints the lines of the file ...

ITERABLE.FOREACH METHOD (JAVA 8)

另一个比较近的方法是Iterable.forEach()方法。在java8中加入。这个方法可以被任何Iterable调用。他支持以一个functional interface座位参数。下面是个例子：

public class IterableForEach \{

public static void main(String\[\] args) \{

Collection c = 1

List.of("One", "Two", "Three"); 2

c.forEach(s -> System.out.println(s)); 3

\}Declare aCollection(aCollectionis anIterable).

Populate it withArrays.of()with an array or sequence of objects (seeRecipe 7.4for how this arbitrary argument list becomes an array).

Invoke the collection’sforEach()method, passing a lambda expression (seeChapter 9for a discussion of hows→System.out.println(s)gets mapped to aConsumerinterface implementation without your even having to import this interface).BothStream.forEachandIterable.forEach()take one argument, of typejava.util.function.Consumer, so they work largely the same way, at least syntactically. This is intentional.

JAVA “FOREACH” LOOP (JAVA 5)

for-loop的语法如下：

for (Type var : Iterable) \{

// do something with "var"\}

for each 可以说是最常用的java code. Iterable可以是任何实现了Iterable的L诶性

JAVA.UTIL.ITERATOR (JAVA 2)

老的Iterator接口有三个方法:

public interface java.util.Iterator \{

public abstract boolean hasNext();

public abstract E next();

public default void remove();

使用方法如下：

Iterator it = ...; // legacy code; might not even have type parameterwhile (it.hasNext()) \{

(MyDataType) c = it.next();

// Do something with c\}

三段式循环

各种教程开始教循环的第一类：

for (init; test; change) \{

// do something\}

基本都是int i=0来开始的

MyDataType\[\] data = ...

for (int i = 0; i < data.length; i++)

MyDataType d = data\[i\];

// do something with it\}

while循环

while循环的好处是，如果是基本变量， 循环结束后变量还在，而for loop中声明的变量在循环后就木有了。

Iterator iterator = ...

while (iterator.hasNext()) \{

MyData md = iterator.next();

//\}

不带重复值的Set

在需要去重，不重复元素列表的时候可以用。Set接口也有add,remove,contains,size,isEmpty方法。但他不会保存排序，他着重的事元素的唯一性。下面是个代码示例：

Set hashSet = new HashSet<>();

hashSet.add("One");

hashSet.add("Two");

hashSet.add("One"); // DUPLICATE hashSet.add("Three");

hashSet.forEach(s -> System.out.println(s));

链表LinkedList

高效的以输入的顺序读取数据的时候非常有用。

下面是个代码示例：

public class LinkedListDemo \{

public static void main(String\[\] argv) \{

System.out.println("Here is a demo of Java's LinkedList class");

LinkedList l = new LinkedList<>();

l.add(new Object().toString());

l.add("Hello");

l.add("end of the list");

System.out.println("Here is a list of all the elements");

l.forEach(o ->

System.out.println("Next element: " + o));

if (l.indexOf("Hello") < 0)

System.err.println("Lookup does not work");

else

System.err.println("Lookup works");

// Now, for added fun, let's walk the linked list backwards. ListIterator li = l.listIterator();

while (li.hasPrevious()) \{

System.out.println("Back to: " + li.previous());

这里使用的LisetIterator是Iterator的子接口。我们可以再看一段代码来理解一下链表是怎么实现的：

public class LinkList implements List \{

/\* A TNode stores one node or item in a Linked List \*/

private static class TNode \{

private TNode next;

private T data;

TNode(T o, TNode next) \{

data = o;

this.next = next;

@Override

public String toString() \{

return String.format("TNode: data='%s', next='%d'", data,

next == null ? 0 : next.hashCode());

private boolean DIAGNOSTIC = false;

/\*\* The root or first TNode in the list; is a dummy pointer,\* so its data will always be null. Simpler this way.\*/

protected TNode first;

/\*\*\* For certain optimizations: A second ref to the last TNode in the list;\* initially == first; always valid (never null), always has next == null.\*/

protected TNode last;

/\*\* Construct a LinkList: initialize the first and last nodes \*/

public LinkList() \{

clear();

/\*\* Construct a LinkList given another Collection.\* This method is recommended by the general contract of List.\*/

public LinkList(Collection c) \{

this();

addAll(c);

/\*\* Set the List (back) to its initial state.\* Any references held will be discarded.\*/

@Override

public void clear() \{

first = new TNode(null, null);

last = first;

/\*\* Add one object to the end of the list. Update the "next"\* reference in the previous end, to refer to the new node.\* Update "last" to refer to the new node.\*/

@Override

public boolean add(T o) \{

last.next = new TNode(o, null);

last = last.next;

return true;

@Override

public void add(int where, T o) \{

TNode t = first;

for (int i=0; i<=where; i++) \{

t = t.next;

if (t == null) \{

throw new IndexOutOfBoundsException(

"'add(n,T) went off end of list");

if (DIAGNOSTIC) \{

System.out.printf("in add(int,T): i = %d, t = %s%n", i, t);

if (DIAGNOSTIC) \{

System.out.printf("in add(int,T): to insert before %s\\n", t);

final TNode nn = new TNode<>(o, t.next);

t.next = nn;

if (DIAGNOSTIC) \{

System.out.printf("add(%d,%s)\\n", where, o);

dump("add(int,T)");

@Override

public boolean addAll(Collection extends T> c) \{

c.forEach(o -> add((T) o));

return false;

@Override

public boolean addAll(int i, Collection extends T> c) \{

AtomicInteger j = new AtomicInteger(i);

c.forEach(o -> \{ add(j.getAndIncrement(), o); \});

return true;

@Override

public boolean contains(Object o) \{

TNode t = first;

while ((t = t.next) != null) \{

if (t.data.equals(o)) \{

return true;

return false;

@Override

public T get(int where) \{

TNode t = first;

int i=0;

// If we get to the end of list before 'where', error out while (i++<=where) \{

if (t.next == null) \{

throw new IndexOutOfBoundsException();

t = t.next;

return t.data;

@Override

public boolean isEmpty() \{

return first == last;

public Iterator iterator() \{

return new Iterator() \{

final int size = size();

int n = 0;

TNode t = first;

/\*\*\* Two cases in which next == null:\* 1) The list is empty, we are at first\* 2) The list is not empty, we are at last.\*/

public boolean hasNext() \{

return n < size;

public T next() \{

if (t == first) \{

t = t.next;

TNode result = t;

t = t.next;

\++n;

return result.data;

public void remove() \{

throw new UnsupportedOperationException("remove");

\};

@Override

public boolean remove(Object o) \{

TNode p = first, prev = null;

while (p != null) \{

if (p.data == o) \{

prev.next = p.next;

return true;

prev = p; p = p.next;

return false;

@Override

public T set(int i, T o) \{

TNode tmp = find(i);

tmp.data = o;

return o;

@Override

public int size() \{

TNode t = first;

int i;

for (i=0; ; i++) \{

if (t == null)

break;

t = t.next;

return i - 1; // subtract one for mandatory head node \}

@SuppressWarnings("unchecked")

public T\[\] toArray(Object\[\] data) \{

// First is an empty anchor, start at its next TNode p = first.next;

for (int i = 0; p != null && i < data.length; i++) \{

data\[i\] = p.data;

p = p.next;

return (T\[\]) data;

public Object\[\] toArray() \{

Object\[\] data = new Object\[size()\];

return toArray(data);

HashTable与HashMap

键值对的数据结构。看个代码示例：

public class HashMapDemo \{

public static void main(String\[\] argv) \{

// Construct and load the hash. This simulates loading a // database or reading from a file, or wherever the data is.

Map map = new HashMap();

// The hash maps from company name to address. // In real life this might map to an Address object... map.put("Adobe", "Mountain View, CA");

map.put("IBM", "White Plains, NY");

map.put("Learning Tree", "Los Angeles, CA");

map.put("Microsoft", "Redmond, WA");

map.put("Netscape", "Mountain View, CA");

map.put("O'Reilly", "Sebastopol, CA");

map.put("Sun", "Mountain View, CA");

// Two versions of the "retrieval" phase. // Version 1: get one pair's value given its key // (presumably the key would really come from user input): String queryString = "O'Reilly";

System.out.println("You asked about " + queryString + ".");

String resultString = map.get(queryString);

System.out.println("They are located in: " + resultString);

System.out.println();

// Version 2: get ALL the keys and values // (maybe to print a report, or to save to disk) for( String key : map.keySet()) \{

System.out.println("Key " + key +

"; Value " + map.get(key));

// Version 3: Same but using a Map.Entry lambda map.entrySet().forEach(mE ->

System.out.println("Key + " + mE.getKey()+

"; Value " +mE.getValue()));

在上面的示例代码中即用了for也有了entrySet来获取一对kv。这对于大型的map来说会快一些，因为他避免了还需要回去拿数据。我们可以也是用Iterator来实现遍历的同时对元素进行删除的处理(What!?)

// Version 2: get ALL the keys and values // with concurrent modification Iterator it = map.keySet().iterator();

while (it.hasNext()) \{

String key = it.next();

if (key.equals("Sun") || key.equals("Netscape")) \{

it.remove();

continue;

System.out.println("Company " + key + "; " +

"Address " + map.get(key));

对Collection进行排序

可以使用Array.sort()或者Collections.sort()

如果数据是在一个array中，可以使用Array.sort搞定

public class SortArray \{

public static void main(String\[\] unused) \{

String\[\] strings = \{

"painful",

"mainly",

"gaining",

"raindrops"

\};

Arrays.sort(strings);

for (int i=0; i

System.out.println(strings\[i\]);

如果排序的结果不是你想要的你可以自己实现一个Comparator并且作为第二个参数传入sort中。java也内置了一些其他排序的方法String.CASE\_INSENSITIVE\_ORDERcan be passed as this second argument. TheStringclass defines it as aComparatorthat ordersStringobjects as bycompareToIgnoreCase. But if you need something fancier, you probably need to write aComparator. In some cases you may be able to use theComparator.comparing()method and other static methods onComparatorto create a custom comparator without having to create a class. Suppose that, for some strange reason, you need to sort strings using all but the first character of the string. One way to do this would be to write thisComparator:

来看一段代码

/\*\* Comparator for comparing strings ignoring first character.\*/

public class SubstringComparator implements Comparator \{

@Override

public int compare(String s1, String s2) \{

s1 = s1.substring(1);

s2 = s2.substring(1);

return s1.compareTo(s2);

// or, more concisely: // return s1.substring(1).compareTo(s2.substring(1)); \}

然后把这个参数传入

public class SubstringComparatorDemo \{

public static void main(String\[\] unused) \{

String\[\] strings = \{

"painful",

"mainly",

"gaining",

"raindrops"

\};

Arrays.sort(strings);

dump(strings, "Using Default Sort");

Arrays.sort(strings, new SubstringComparator());

dump(strings, "Using SubstringComparator");

// tag::functional\[\] System.out.println("Functional approach:");

Arrays.stream(strings)

.sorted(Comparator.comparing(s->s.substring(1)))

.forEach(System.out::println);

// end::functional\[\] \}

static void dump(String\[\] args, String title) \{

System.out.println(title);

for (String s : args)

System.out.println(s);

Collection的元素查找

下面是不同的implementing class对应的查找方法：注意binarySearch只能对排序完毕的算法使用，所以可以先call Arrays.sort()方法.

将Collections对象转为Array

一般使用toArray()方法即可。

我们可以通过collections.toArray()方法转换(默认都是转为Object\[\])如果有需求的话，可以提供一个array agrument：决定了返回的数组的数据类型

保证数组的大小够大。如果大小不够的话，会自动创建一个新的array. 如果类型不兼容，会得到一个ArrayStoreException

来看个示例代码

List list = new ArrayList<>();

list.add("Blobbo");

list.add("Cracked");

list.add("Dumbo");

// Convert a collection to Object\[\], which can store objects // of any type. Object\[\] ol = list.toArray();

System.out.println("Array of Object has length " + ol.length);

String\[\] sl = (String\[\]) list.toArray(new String\[0\]);

System.out.println("Array of String has length " + sl.length);

使自己的数据结构支持迭代

为了使自己的的数据结构支持迭代，你的class必须implement iterable.一个Iterator有三哥方法：hasNext,next() remove。下面来看个代码示例

public class IterableDemo \{

/\*\* Demo implements Iterable, meaning it must provide an Iterator,\* and that it can be used in a foreach loop.\*/

static class Demo implements Iterable \{

// Simple demo: use array instead of inventing new data structure String\[\] data = \{ "One", "Two", "Three"\};

/\*\* This is the Iterator that makes it all happen \*/

class DemoIterator implements Iterator \{

int i = 0;

/\*\*\* Tell if there are any more elements.\* @return true if next() will succeed, false otherwise\*/

public boolean hasNext() \{

return i < data.length;

/\*\* @return the next element from the data \*/

public String next() \{

return data\[i++\];

/\*\* Remove the object that next() just returned.\* An Iterator is not required to support this interface, and we don't.\* @throws UnsupportedOperationException unconditionally\*/

public void remove() \{

throw new UnsupportedOperationException("remove");

/\*\* Method by which the Demo class makes its iterator available \*/

public Iterator iterator() \{

return new DemoIterator();

public static void main(String\[\] args) \{

Demo demo = new Demo();

for (String s : demo) \{

System.out.println(s);

结束本章是下书的学习笔记，Java可太麻烦了...https://learning.oreilly.com/library/view/java-cookbook-4th/9781492072577/ch07.html\#javacook-structurelearning.oreilly.com![348a58e2ad0140ed75769b625852341d.png][]Java Cookbook, 4th Editionlearning.oreilly.com![348a58e2ad0140ed75769b625852341d.png][]

[2b169c55ec5abe563f206c84cb22932f.png]: /images/20221023/99ef21d915534458a67cf331f66027ba.png
[348a58e2ad0140ed75769b625852341d.png]: /images/20221023/2be4098272834bef867ece9316c2b9f6.png