jupyter/Appendix-Collection-Topics.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[TOC]\n",
    "\n",
    "<!-- Appendix: Collection Topics -->\n",
    "# 附录:集合主题\n",
    "\n",
    "> 本附录是一些比[第十二章 集合]()中介绍的更高级的内容。\n",
    "\n",
    "<!-- Sample Data -->\n",
    "## 示例数据\n",
    "\n",
    "这里创建一些样本数据用于集合示例。 以下数据将颜色名称与HTML颜色的RGB值相关联。请注意，每个键和值都是唯一的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// onjava/HTMLColors.java\n",
    "// Sample data for collection examples\n",
    "package onjava;\n",
    "import java.util.*;\n",
    "import java.util.stream.*;\n",
    "import java.util.concurrent.*;\n",
    "\n",
    "public class HTMLColors {\n",
    "  public static final Object[][] ARRAY = {\n",
    "    { 0xF0F8FF, \"AliceBlue\" },\n",
    "    { 0xFAEBD7, \"AntiqueWhite\" },\n",
    "    { 0x7FFFD4, \"Aquamarine\" },\n",
    "    { 0xF0FFFF, \"Azure\" },\n",
    "    { 0xF5F5DC, \"Beige\" },\n",
    "    { 0xFFE4C4, \"Bisque\" },\n",
    "    { 0x000000, \"Black\" },\n",
    "    { 0xFFEBCD, \"BlanchedAlmond\" },\n",
    "    { 0x0000FF, \"Blue\" },\n",
    "    { 0x8A2BE2, \"BlueViolet\" },\n",
    "    { 0xA52A2A, \"Brown\" },\n",
    "    { 0xDEB887, \"BurlyWood\" },\n",
    "    { 0x5F9EA0, \"CadetBlue\" },\n",
    "    { 0x7FFF00, \"Chartreuse\" },\n",
    "    { 0xD2691E, \"Chocolate\" },\n",
    "    { 0xFF7F50, \"Coral\" },\n",
    "    { 0x6495ED, \"CornflowerBlue\" },\n",
    "    { 0xFFF8DC, \"Cornsilk\" },\n",
    "    { 0xDC143C, \"Crimson\" },\n",
    "    { 0x00FFFF, \"Cyan\" },\n",
    "    { 0x00008B, \"DarkBlue\" },\n",
    "    { 0x008B8B, \"DarkCyan\" },\n",
    "    { 0xB8860B, \"DarkGoldenRod\" },\n",
    "    { 0xA9A9A9, \"DarkGray\" },\n",
    "    { 0x006400, \"DarkGreen\" },\n",
    "    { 0xBDB76B, \"DarkKhaki\" },\n",
    "    { 0x8B008B, \"DarkMagenta\" },\n",
    "    { 0x556B2F, \"DarkOliveGreen\" },\n",
    "    { 0xFF8C00, \"DarkOrange\" },\n",
    "    { 0x9932CC, \"DarkOrchid\" },\n",
    "    { 0x8B0000, \"DarkRed\" },\n",
    "    { 0xE9967A, \"DarkSalmon\" },\n",
    "    { 0x8FBC8F, \"DarkSeaGreen\" },\n",
    "    { 0x483D8B, \"DarkSlateBlue\" },\n",
    "    { 0x2F4F4F, \"DarkSlateGray\" },\n",
    "    { 0x00CED1, \"DarkTurquoise\" },\n",
    "    { 0x9400D3, \"DarkViolet\" },\n",
    "    { 0xFF1493, \"DeepPink\" },\n",
    "    { 0x00BFFF, \"DeepSkyBlue\" },\n",
    "    { 0x696969, \"DimGray\" },\n",
    "    { 0x1E90FF, \"DodgerBlue\" },\n",
    "    { 0xB22222, \"FireBrick\" },\n",
    "    { 0xFFFAF0, \"FloralWhite\" },\n",
    "    { 0x228B22, \"ForestGreen\" },\n",
    "    { 0xDCDCDC, \"Gainsboro\" },\n",
    "    { 0xF8F8FF, \"GhostWhite\" },\n",
    "    { 0xFFD700, \"Gold\" },\n",
    "    { 0xDAA520, \"GoldenRod\" },\n",
    "    { 0x808080, \"Gray\" },\n",
    "    { 0x008000, \"Green\" },\n",
    "    { 0xADFF2F, \"GreenYellow\" },\n",
    "    { 0xF0FFF0, \"HoneyDew\" },\n",
    "    { 0xFF69B4, \"HotPink\" },\n",
    "    { 0xCD5C5C, \"IndianRed\" },\n",
    "    { 0x4B0082, \"Indigo\" },\n",
    "    { 0xFFFFF0, \"Ivory\" },\n",
    "    { 0xF0E68C, \"Khaki\" },\n",
    "    { 0xE6E6FA, \"Lavender\" },\n",
    "    { 0xFFF0F5, \"LavenderBlush\" },\n",
    "    { 0x7CFC00, \"LawnGreen\" },\n",
    "    { 0xFFFACD, \"LemonChiffon\" },\n",
    "    { 0xADD8E6, \"LightBlue\" },\n",
    "    { 0xF08080, \"LightCoral\" },\n",
    "    { 0xE0FFFF, \"LightCyan\" },\n",
    "    { 0xFAFAD2, \"LightGoldenRodYellow\" },\n",
    "    { 0xD3D3D3, \"LightGray\" },\n",
    "    { 0x90EE90, \"LightGreen\" },\n",
    "    { 0xFFB6C1, \"LightPink\" },\n",
    "    { 0xFFA07A, \"LightSalmon\" },\n",
    "    { 0x20B2AA, \"LightSeaGreen\" },\n",
    "    { 0x87CEFA, \"LightSkyBlue\" },\n",
    "    { 0x778899, \"LightSlateGray\" },\n",
    "    { 0xB0C4DE, \"LightSteelBlue\" },\n",
    "    { 0xFFFFE0, \"LightYellow\" },\n",
    "    { 0x00FF00, \"Lime\" },\n",
    "    { 0x32CD32, \"LimeGreen\" },\n",
    "    { 0xFAF0E6, \"Linen\" },\n",
    "    { 0xFF00FF, \"Magenta\" },\n",
    "    { 0x800000, \"Maroon\" },\n",
    "    { 0x66CDAA, \"MediumAquaMarine\" },\n",
    "    { 0x0000CD, \"MediumBlue\" },\n",
    "    { 0xBA55D3, \"MediumOrchid\" },\n",
    "    { 0x9370DB, \"MediumPurple\" },\n",
    "    { 0x3CB371, \"MediumSeaGreen\" },\n",
    "    { 0x7B68EE, \"MediumSlateBlue\" },\n",
    "    { 0x00FA9A, \"MediumSpringGreen\" },\n",
    "    { 0x48D1CC, \"MediumTurquoise\" },\n",
    "    { 0xC71585, \"MediumVioletRed\" },\n",
    "    { 0x191970, \"MidnightBlue\" },\n",
    "    { 0xF5FFFA, \"MintCream\" },\n",
    "    { 0xFFE4E1, \"MistyRose\" },\n",
    "    { 0xFFE4B5, \"Moccasin\" },\n",
    "    { 0xFFDEAD, \"NavajoWhite\" },\n",
    "    { 0x000080, \"Navy\" },\n",
    "    { 0xFDF5E6, \"OldLace\" },\n",
    "    { 0x808000, \"Olive\" },\n",
    "    { 0x6B8E23, \"OliveDrab\" },\n",
    "    { 0xFFA500, \"Orange\" },\n",
    "    { 0xFF4500, \"OrangeRed\" },\n",
    "    { 0xDA70D6, \"Orchid\" },\n",
    "    { 0xEEE8AA, \"PaleGoldenRod\" },\n",
    "    { 0x98FB98, \"PaleGreen\" },\n",
    "    { 0xAFEEEE, \"PaleTurquoise\" },\n",
    "    { 0xDB7093, \"PaleVioletRed\" },\n",
    "    { 0xFFEFD5, \"PapayaWhip\" },\n",
    "    { 0xFFDAB9, \"PeachPuff\" },\n",
    "    { 0xCD853F, \"Peru\" },\n",
    "    { 0xFFC0CB, \"Pink\" },\n",
    "    { 0xDDA0DD, \"Plum\" },\n",
    "    { 0xB0E0E6, \"PowderBlue\" },\n",
    "    { 0x800080, \"Purple\" },\n",
    "    { 0xFF0000, \"Red\" },\n",
    "    { 0xBC8F8F, \"RosyBrown\" },\n",
    "    { 0x4169E1, \"RoyalBlue\" },\n",
    "    { 0x8B4513, \"SaddleBrown\" },\n",
    "    { 0xFA8072, \"Salmon\" },\n",
    "    { 0xF4A460, \"SandyBrown\" },\n",
    "    { 0x2E8B57, \"SeaGreen\" },\n",
    "    { 0xFFF5EE, \"SeaShell\" },\n",
    "    { 0xA0522D, \"Sienna\" },\n",
    "    { 0xC0C0C0, \"Silver\" },\n",
    "    { 0x87CEEB, \"SkyBlue\" },\n",
    "    { 0x6A5ACD, \"SlateBlue\" },\n",
    "    { 0x708090, \"SlateGray\" },\n",
    "    { 0xFFFAFA, \"Snow\" },\n",
    "    { 0x00FF7F, \"SpringGreen\" },\n",
    "    { 0x4682B4, \"SteelBlue\" },\n",
    "    { 0xD2B48C, \"Tan\" },\n",
    "    { 0x008080, \"Teal\" },\n",
    "    { 0xD8BFD8, \"Thistle\" },\n",
    "    { 0xFF6347, \"Tomato\" },\n",
    "    { 0x40E0D0, \"Turquoise\" },\n",
    "    { 0xEE82EE, \"Violet\" },\n",
    "    { 0xF5DEB3, \"Wheat\" },\n",
    "    { 0xFFFFFF, \"White\" },\n",
    "    { 0xF5F5F5, \"WhiteSmoke\" },\n",
    "    { 0xFFFF00, \"Yellow\" },\n",
    "    { 0x9ACD32, \"YellowGreen\" },\n",
    "  };\n",
    "  public static final Map<Integer,String> MAP =\n",
    "    Arrays.stream(ARRAY)\n",
    "      .collect(Collectors.toMap(\n",
    "        element -> (Integer)element[0],\n",
    "        element -> (String)element[1],\n",
    "        (v1, v2) -> { // Merge function\n",
    "          throw new IllegalStateException();\n",
    "        },\n",
    "        LinkedHashMap::new\n",
    "      ));\n",
    "  // Inversion only works if values are unique:\n",
    "  public static <V, K> Map<V, K>\n",
    "  invert(Map<K, V> map) {\n",
    "    return map.entrySet().stream()\n",
    "      .collect(Collectors.toMap(\n",
    "        Map.Entry::getValue,\n",
    "        Map.Entry::getKey,\n",
    "        (v1, v2) -> {\n",
    "          throw new IllegalStateException();\n",
    "        },\n",
    "        LinkedHashMap::new\n",
    "      ));\n",
    "  }\n",
    "  public static final Map<String,Integer>\n",
    "    INVMAP = invert(MAP);\n",
    "  // Look up RGB value given a name:\n",
    "  public static Integer rgb(String colorName) {\n",
    "    return INVMAP.get(colorName);\n",
    "  }\n",
    "  public static final List<String> LIST =\n",
    "    Arrays.stream(ARRAY)\n",
    "      .map(item -> (String)item[1])\n",
    "      .collect(Collectors.toList());\n",
    "  public static final List<Integer> RGBLIST =\n",
    "    Arrays.stream(ARRAY)\n",
    "      .map(item -> (Integer)item[0])\n",
    "      .collect(Collectors.toList());\n",
    "  public static\n",
    "  void show(Map.Entry<Integer,String> e) {\n",
    "    System.out.format(\n",
    "      \"0x%06X: %s%n\", e.getKey(), e.getValue());\n",
    "  }\n",
    "  public static void\n",
    "  show(Map<Integer,String> m, int count) {\n",
    "    m.entrySet().stream()\n",
    "      .limit(count)\n",
    "      .forEach(e -> show(e));\n",
    "  }\n",
    "  public static void show(Map<Integer,String> m) {\n",
    "    show(m, m.size());\n",
    "  }\n",
    "  public static\n",
    "  void show(Collection<String> lst, int count) {\n",
    "    lst.stream()\n",
    "      .limit(count)\n",
    "      .forEach(System.out::println);\n",
    "  }\n",
    "  public static void show(Collection<String> lst) {\n",
    "    show(lst, lst.size());\n",
    "  }\n",
    "  public static\n",
    "  void showrgb(Collection<Integer> lst, int count) {\n",
    "    lst.stream()\n",
    "      .limit(count)\n",
    "      .forEach(n -> System.out.format(\"0x%06X%n\", n));\n",
    "  }\n",
    "  public static void showrgb(Collection<Integer> lst) {\n",
    "    showrgb(lst, lst.size());\n",
    "  }\n",
    "  public static\n",
    "  void showInv(Map<String,Integer> m, int count) {\n",
    "    m.entrySet().stream()\n",
    "      .limit(count)\n",
    "      .forEach(e ->\n",
    "        System.out.format(\n",
    "          \"%-20s  0x%06X%n\", e.getKey(), e.getValue()));\n",
    "  }\n",
    "  public static void showInv(Map<String,Integer> m) {\n",
    "    showInv(m, m.size());\n",
    "  }\n",
    "  public static void border() {\n",
    "    System.out.println(\n",
    "      \"******************************\");\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**MAP** 是使用Streams（[第十四章 流式编程]()）创建的。 二维数组 **ARRAY** 作为流传输到 **Map** 中，但请注意我们不仅仅是使用简单版本的 `Collectors.toMap()` 。 那个版本生成一个 **HashMap** ，它使用散列函数来控制对键的排序。 为了保留原来的顺序，我们必须将键值对直接放入 **TreeMap** 中，这意味着我们需要使用更复杂的 `Collectors.toMap()` 版本。这需要两个函数从每个流元素中提取键和值，就像简单版本的`Collectors.toMap()` 一样。 然后它需要一个*合并函数*（merge function），它解决了与同一个键相关的两个值之间的冲突。这里的数据已经预先审查过，因此绝不会发生这种情况，如果有的话，这里会抛出异常。最后，传递生成所需类型的空map的函数，然后用流来填充它。\n",
    "\n",
    "`rgb()` 方法是一个便捷函数（convenience function），它接受颜色名称 **String** 参数并生成其数字RGB值。为此，我们需要一个反转版本的 **COLORS** ，它接受一个 **String**键并查找RGB的 **Integer** 值。 这是通过 `invert()` 方法实现的，如果任何 **COLORS** 值不唯一，则抛出异常。\n",
    "\n",
    "我们还创建包含所有名称的 **LIST** ，以及包含十六进制表示法的RGB值的 **RGBLIST** 。\n",
    "\n",
    "第一个 `show()` 方法接受一个 **Map.Entry** 并显示以十六进制表示的键，以便轻松地对原始 **ARRAY** 进行双重检查。 名称以 **show** 开头的每个方法都会重载两个版本，其中一个版本采用 **count** 参数来指示要显示的元素数量，第二个版本显示序列中的所有元素。\n",
    "\n",
    "这里是一个基本的测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/HTMLColorTest.java\n",
    "import static onjava.HTMLColors.*;\n",
    "\n",
    "public class HTMLColorTest {\n",
    "  static final int DISPLAY_SIZE = 20;\n",
    "  public static void main(String[] args) {\n",
    "    show(MAP, DISPLAY_SIZE);\n",
    "    border();\n",
    "    showInv(INVMAP, DISPLAY_SIZE);\n",
    "    border();\n",
    "    show(LIST, DISPLAY_SIZE);\n",
    "    border();\n",
    "    showrgb(RGBLIST, DISPLAY_SIZE);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "0xF0F8FF: AliceBlue\n",
    "0xFAEBD7: AntiqueWhite\n",
    "0x7FFFD4: Aquamarine\n",
    "0xF0FFFF: Azure\n",
    "0xF5F5DC: Beige\n",
    "0xFFE4C4: Bisque\n",
    "0x000000: Black\n",
    "0xFFEBCD: BlanchedAlmond\n",
    "0x0000FF: Blue\n",
    "0x8A2BE2: BlueViolet\n",
    "0xA52A2A: Brown\n",
    "0xDEB887: BurlyWood\n",
    "0x5F9EA0: CadetBlue\n",
    "0x7FFF00: Chartreuse\n",
    "0xD2691E: Chocolate\n",
    "0xFF7F50: Coral\n",
    "0x6495ED: CornflowerBlue\n",
    "0xFFF8DC: Cornsilk\n",
    "0xDC143C: Crimson\n",
    "0x00FFFF: Cyan\n",
    "******************************\n",
    "AliceBlue             0xF0F8FF\n",
    "AntiqueWhite          0xFAEBD7\n",
    "Aquamarine            0x7FFFD4\n",
    "Azure                 0xF0FFFF\n",
    "Beige                 0xF5F5DC\n",
    "Bisque                0xFFE4C4\n",
    "Black                 0x000000\n",
    "BlanchedAlmond        0xFFEBCD\n",
    "Blue                  0x0000FF\n",
    "BlueViolet            0x8A2BE2\n",
    "Brown                 0xA52A2A\n",
    "BurlyWood             0xDEB887\n",
    "CadetBlue             0x5F9EA0\n",
    "Chartreuse            0x7FFF00\n",
    "Chocolate             0xD2691E\n",
    "Coral                 0xFF7F50\n",
    "CornflowerBlue        0x6495ED\n",
    "Cornsilk              0xFFF8DC\n",
    "Crimson               0xDC143C\n",
    "Cyan                  0x00FFFF\n",
    "******************************\n",
    "AliceBlue\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "Beige\n",
    "Bisque\n",
    "Black\n",
    "BlanchedAlmond\n",
    "Blue\n",
    "BlueViolet\n",
    "Brown\n",
    "BurlyWood\n",
    "CadetBlue\n",
    "Chartreuse\n",
    "Chocolate\n",
    "Coral\n",
    "CornflowerBlue\n",
    "Cornsilk\n",
    "Crimson\n",
    "Cyan\n",
    "******************************\n",
    "0xF0F8FF\n",
    "0xFAEBD7\n",
    "0x7FFFD4\n",
    "0xF0FFFF\n",
    "0xF5F5DC\n",
    "0xFFE4C4\n",
    "0x000000\n",
    "0xFFEBCD\n",
    "0x0000FF\n",
    "0x8A2BE2\n",
    "0xA52A2A\n",
    "0xDEB887\n",
    "0x5F9EA0\n",
    "0x7FFF00\n",
    "0xD2691E\n",
    "0xFF7F50\n",
    "0x6495ED\n",
    "0xFFF8DC\n",
    "0xDC143C\n",
    "0x00FFFF\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，使用 **LinkedHashMap** 确实能够保留 **HTMLColors.ARRAY** 的顺序。\n",
    "\n",
    "<!-- List Behavior -->\n",
    "## List行为\n",
    "\n",
    "**Lists** 是存储和检索对象（次于数组）的最基本方法。基本列表操作包括：\n",
    "\n",
    "- `add()` 用于插入元素\n",
    "- `get()` 用于随机访问元素\n",
    "- `iterator()` 获取序列上的一个 **Iterator**\n",
    "- `stream()` 生成元素的一个 **Stream**\n",
    "\n",
    "列表构造方法始终保留元素的添加顺序。\n",
    "\n",
    "以下示例中的方法各自涵盖了一组不同的行为：每个 **List** 可以执行的操作（ `basicTest()` ），使用 **Iterator** （ `iterMotion()` ）遍历序列，使用 **Iterator** （ `iterManipulation()` ）更改内容，查看 **List** 操作（ `testVisual()` ）的效果，以及仅可用于 **LinkedLists** 的操作："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/ListOps.java\n",
    "// Things you can do with Lists\n",
    "import java.util.*;\n",
    "import onjava.HTMLColors;\n",
    "\n",
    "public class ListOps {\n",
    "  // Create a short list for testing:\n",
    "  static final List<String> LIST =\n",
    "    HTMLColors.LIST.subList(0, 10);\n",
    "  private static boolean b;\n",
    "  private static String s;\n",
    "  private static int i;\n",
    "  private static Iterator<String> it;\n",
    "  private static ListIterator<String> lit;\n",
    "  public static void basicTest(List<String> a) {\n",
    "    a.add(1, \"x\"); // Add at location 1\n",
    "    a.add(\"x\"); // Add at end\n",
    "    // Add a collection:\n",
    "    a.addAll(LIST);\n",
    "    // Add a collection starting at location 3:\n",
    "    a.addAll(3, LIST);\n",
    "    b = a.contains(\"1\"); // Is it in there?\n",
    "    // Is the entire collection in there?\n",
    "    b = a.containsAll(LIST);\n",
    "    // Lists allow random access, which is cheap\n",
    "    // for ArrayList, expensive for LinkedList:\n",
    "    s = a.get(1); // Get (typed) object at location 1\n",
    "    i = a.indexOf(\"1\"); // Tell index of object\n",
    "    b = a.isEmpty(); // Any elements inside?\n",
    "    it = a.iterator(); // Ordinary Iterator\n",
    "    lit = a.listIterator(); // ListIterator\n",
    "    lit = a.listIterator(3); // Start at location 3\n",
    "    i = a.lastIndexOf(\"1\"); // Last match\n",
    "    a.remove(1); // Remove location 1\n",
    "    a.remove(\"3\"); // Remove this object\n",
    "    a.set(1, \"y\"); // Set location 1 to \"y\"\n",
    "    // Keep everything that's in the argument\n",
    "    // (the intersection of the two sets):\n",
    "    a.retainAll(LIST);\n",
    "    // Remove everything that's in the argument:\n",
    "    a.removeAll(LIST);\n",
    "    i = a.size(); // How big is it?\n",
    "    a.clear(); // Remove all elements\n",
    "  }\n",
    "  public static void iterMotion(List<String> a) {\n",
    "    ListIterator<String> it = a.listIterator();\n",
    "    b = it.hasNext();\n",
    "    b = it.hasPrevious();\n",
    "    s = it.next();\n",
    "    i = it.nextIndex();\n",
    "    s = it.previous();\n",
    "    i = it.previousIndex();\n",
    "  }\n",
    "  public static void iterManipulation(List<String> a) {\n",
    "    ListIterator<String> it = a.listIterator();\n",
    "    it.add(\"47\");\n",
    "    // Must move to an element after add():\n",
    "    it.next();\n",
    "    // Remove the element after the new one:\n",
    "    it.remove();\n",
    "    // Must move to an element after remove():\n",
    "    it.next();\n",
    "    // Change the element after the deleted one:\n",
    "    it.set(\"47\");\n",
    "  }\n",
    "  public static void testVisual(List<String> a) {\n",
    "    System.out.println(a);\n",
    "    List<String> b = LIST;\n",
    "    System.out.println(\"b = \" + b);\n",
    "    a.addAll(b);\n",
    "    a.addAll(b);\n",
    "    System.out.println(a);\n",
    "    // Insert, remove, and replace elements\n",
    "    // using a ListIterator:\n",
    "    ListIterator<String> x =\n",
    "      a.listIterator(a.size()/2);\n",
    "    x.add(\"one\");\n",
    "    System.out.println(a);\n",
    "    System.out.println(x.next());\n",
    "    x.remove();\n",
    "    System.out.println(x.next());\n",
    "    x.set(\"47\");\n",
    "    System.out.println(a);\n",
    "    // Traverse the list backwards:\n",
    "    x = a.listIterator(a.size());\n",
    "    while(x.hasPrevious())\n",
    "      System.out.print(x.previous() + \" \");\n",
    "    System.out.println();\n",
    "    System.out.println(\"testVisual finished\");\n",
    "  }\n",
    "  // There are some things that only LinkedLists can do:\n",
    "  public static void testLinkedList() {\n",
    "    LinkedList<String> ll = new LinkedList<>();\n",
    "    ll.addAll(LIST);\n",
    "    System.out.println(ll);\n",
    "    // Treat it like a stack, pushing:\n",
    "    ll.addFirst(\"one\");\n",
    "    ll.addFirst(\"two\");\n",
    "    System.out.println(ll);\n",
    "    // Like \"peeking\" at the top of a stack:\n",
    "    System.out.println(ll.getFirst());\n",
    "    // Like popping a stack:\n",
    "    System.out.println(ll.removeFirst());\n",
    "    System.out.println(ll.removeFirst());\n",
    "    // Treat it like a queue, pulling elements\n",
    "    // off the tail end:\n",
    "    System.out.println(ll.removeLast());\n",
    "    System.out.println(ll);\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    // Make and fill a new list each time:\n",
    "    basicTest(new LinkedList<>(LIST));\n",
    "    basicTest(new ArrayList<>(LIST));\n",
    "    iterMotion(new LinkedList<>(LIST));\n",
    "    iterMotion(new ArrayList<>(LIST));\n",
    "    iterManipulation(new LinkedList<>(LIST));\n",
    "    iterManipulation(new ArrayList<>(LIST));\n",
    "    testVisual(new LinkedList<>(LIST));\n",
    "    testLinkedList();\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet]\n",
    "b = [AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet]\n",
    "[AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet,\n",
    "AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet,\n",
    "AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet]\n",
    "[AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet,\n",
    "AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige, one,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet,\n",
    "AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet]\n",
    "Bisque\n",
    "Black\n",
    "[AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet,\n",
    "AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige, one,\n",
    "47, BlanchedAlmond, Blue, BlueViolet, AliceBlue,\n",
    "AntiqueWhite, Aquamarine, Azure, Beige, Bisque, Black,\n",
    "BlanchedAlmond, Blue, BlueViolet]\n",
    "BlueViolet Blue BlanchedAlmond Black Bisque Beige Azure\n",
    "Aquamarine AntiqueWhite AliceBlue BlueViolet Blue\n",
    "BlanchedAlmond 47 one Beige Azure Aquamarine\n",
    "AntiqueWhite AliceBlue BlueViolet Blue BlanchedAlmond\n",
    "Black Bisque Beige Azure Aquamarine AntiqueWhite\n",
    "AliceBlue\n",
    "testVisual finished\n",
    "[AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue, BlueViolet]\n",
    "[two, one, AliceBlue, AntiqueWhite, Aquamarine, Azure,\n",
    "Beige, Bisque, Black, BlanchedAlmond, Blue, BlueViolet]\n",
    "two\n",
    "two\n",
    "one\n",
    "BlueViolet\n",
    "[AliceBlue, AntiqueWhite, Aquamarine, Azure, Beige,\n",
    "Bisque, Black, BlanchedAlmond, Blue]\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 `basicTest()` 和 `iterMotion()` 中，方法调用是为了展示正确的语法，尽管获取了返回值，但不会使用它。在某些情况下，根本不会去获取返回值。在使用这些方法之前，请查看JDK文档中这些方法的完整用法。\n",
    "\n",
    "<!-- Set Behavior -->\n",
    "## Set行为\n",
    "\n",
    "**Set** 的主要用处是测试成员身份，不过也可以将其用作删除重复元素的工具。如果不关心元素顺序或并发性， **HashSet** 总是最好的选择，因为它是专门为了快速查找而设计的（这里使用了在[附录：理解equals和hashCode方法]()章节中探讨的散列函数）。\n",
    "\n",
    "其它的 **Set** 实现产生不同的排序行为："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/SetOrder.java\n",
    "import java.util.*;\n",
    "import onjava.HTMLColors;\n",
    "\n",
    "public class SetOrder {\n",
    "  static String[] sets = {\n",
    "    \"java.util.HashSet\",\n",
    "    \"java.util.TreeSet\",\n",
    "    \"java.util.concurrent.ConcurrentSkipListSet\",\n",
    "    \"java.util.LinkedHashSet\",\n",
    "    \"java.util.concurrent.CopyOnWriteArraySet\",\n",
    "  };\n",
    "  static final List<String> RLIST =\n",
    "    new ArrayList<>(HTMLColors.LIST);\n",
    "  static {\n",
    "    Collections.reverse(RLIST);\n",
    "  }\n",
    "  public static void\n",
    "  main(String[] args) throws Exception {\n",
    "    for(String type: sets) {\n",
    "      System.out.format(\"[-> %s <-]%n\",\n",
    "        type.substring(type.lastIndexOf('.') + 1));\n",
    "      @SuppressWarnings(\"unchecked\")\n",
    "      Set<String> set = (Set<String>)\n",
    "        Class.forName(type).newInstance();\n",
    "      set.addAll(RLIST);\n",
    "      set.stream()\n",
    "        .limit(10)\n",
    "        .forEach(System.out::println);\n",
    "    }\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[-> HashSet <-]\n",
    "MediumOrchid\n",
    "PaleGoldenRod\n",
    "Sienna\n",
    "LightSlateGray\n",
    "DarkSeaGreen\n",
    "Black\n",
    "Gainsboro\n",
    "Orange\n",
    "LightCoral\n",
    "DodgerBlue\n",
    "[-> TreeSet <-]\n",
    "AliceBlue\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "Beige\n",
    "Bisque\n",
    "Black\n",
    "BlanchedAlmond\n",
    "Blue\n",
    "BlueViolet\n",
    "[-> ConcurrentSkipListSet <-]\n",
    "AliceBlue\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "Beige\n",
    "Bisque\n",
    "Black\n",
    "BlanchedAlmond\n",
    "Blue\n",
    "BlueViolet\n",
    "[-> LinkedHashSet <-]\n",
    "YellowGreen\n",
    "Yellow\n",
    "WhiteSmoke\n",
    "White\n",
    "Wheat\n",
    "Violet\n",
    "Turquoise\n",
    "Tomato\n",
    "Thistle\n",
    "Teal\n",
    "[-> CopyOnWriteArraySet <-]\n",
    "YellowGreen\n",
    "Yellow\n",
    "WhiteSmoke\n",
    "White\n",
    "Wheat\n",
    "Violet\n",
    "Turquoise\n",
    "Tomato\n",
    "Thistle\n",
    "Teal\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里需要使用 **@SuppressWarnings(“unchecked”)** ，因为这里将一个 **String** （可能是任何东西）传递给了 `Class.forName(type).newInstance()` 。编译器并不能保证这是一次成功的操作。\n",
    "\n",
    "**RLIST** 是 **HTMLColors.LIST** 的反转版本。因为 `Collections.reverse()` 是通过修改参数来执行反向操作，而不是返回包含反向元素的新 **List** ，所以该调用在 **static** 块内执行。  **RLIST** 可以防止我们意外地认为 **Set** 对其结果进行了排序。\n",
    "\n",
    "**HashSet** 的输出结果似乎没有可辨别的顺序，因为它是基于散列函数的。 **TreeSet** 和 **ConcurrentSkipListSet** 都对它们的元素进行了排序，它们都实现了 **SortedSet** 接口来标识这个特点。因为实现该接口的 **Set** 按顺序排列，所以该接口还有一些其他的可用操作。 **LinkedHashSet** 和 **CopyOnWriteArraySet** 尽管没有用于标识的接口，但它们还是保留了元素的插入顺序。\n",
    "\n",
    "**ConcurrentSkipListSet** 和 **CopyOnWriteArraySet** 是线程安全的。\n",
    "\n",
    "在附录的最后，我们将了解在非 **HashSet** 实现的 **Set** 上添加额外排序的性能成本，以及不同实现中的任何其他功能的成本。\n",
    "\n",
    "<!-- Using Functional Operations with any Map -->\n",
    "## 在Map中使用函数式操作\n",
    "\n",
    "与 **Collection** 接口一样，`forEach()` 也内置在 **Map** 接口中。但是如果想要执行任何其他的基本功能操作，比如 `map()` ，`flatMap()` ，`reduce()` 或 `filter()` 时，该怎么办？ 查看 **Map** 接口发现并没有这些。\n",
    "\n",
    "可以通过 `entrySet()` 连接到这些方法，该方法会生成一个由 **Map.Entry** 对象组成的 **Set** 。这个 **Set** 包含 `stream()` 和 `parallelStream()` 方法。只需要记住一件事，这里正在使用的是 **Map.Entry** 对象："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/FunctionalMap.java\n",
    "// Functional operations on a Map\n",
    "import java.util.*;\n",
    "import java.util.stream.*;\n",
    "import java.util.concurrent.*;\n",
    "import static onjava.HTMLColors.*;\n",
    "\n",
    "public class FunctionalMap {\n",
    "  public static void main(String[] args) {\n",
    "    MAP.entrySet().stream()\n",
    "      .map(Map.Entry::getValue)\n",
    "      .filter(v -> v.startsWith(\"Dark\"))\n",
    "      .map(v -> v.replaceFirst(\"Dark\", \"Hot\"))\n",
    "      .forEach(System.out::println);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "HotBlue\n",
    "HotCyan\n",
    "HotGoldenRod\n",
    "HotGray\n",
    "HotGreen\n",
    "HotKhaki\n",
    "HotMagenta\n",
    "HotOliveGreen\n",
    "HotOrange\n",
    "HotOrchid\n",
    "HotRed\n",
    "HotSalmon\n",
    "HotSeaGreen\n",
    "HotSlateBlue\n",
    "HotSlateGray\n",
    "HotTurquoise\n",
    "HotViolet\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "生成 **Stream** 后，所有的基本功能方法，甚至更多就都可以使用了。\n",
    "\n",
    "<!-- Selecting Parts of a Map -->\n",
    "## 选择Map片段\n",
    "\n",
    "由 **TreeMap** 和 **ConcurrentSkipListMap** 实现的 **NavigableMap** 接口解决了需要选择Map片段的问题。下面是一个示例，使用了 **HTMLColors** ："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/NavMap.java\n",
    "// NavigableMap produces pieces of a Map\n",
    "import java.util.*;\n",
    "import java.util.concurrent.*;\n",
    "import static onjava.HTMLColors.*;\n",
    "\n",
    "public class NavMap {\n",
    "  public static final\n",
    "  NavigableMap<Integer,String> COLORS =\n",
    "    new ConcurrentSkipListMap<>(MAP);\n",
    "  public static void main(String[] args) {\n",
    "    show(COLORS.firstEntry());\n",
    "    border();\n",
    "    show(COLORS.lastEntry());\n",
    "    border();\n",
    "    NavigableMap<Integer, String> toLime =\n",
    "      COLORS.headMap(rgb(\"Lime\"), true);\n",
    "    show(toLime);\n",
    "    border();\n",
    "    show(COLORS.ceilingEntry(rgb(\"DeepSkyBlue\") - 1));\n",
    "    border();\n",
    "    show(COLORS.floorEntry(rgb(\"DeepSkyBlue\") - 1));\n",
    "    border();\n",
    "    show(toLime.descendingMap());\n",
    "    border();\n",
    "    show(COLORS.tailMap(rgb(\"MistyRose\"), true));\n",
    "    border();\n",
    "    show(COLORS.subMap(\n",
    "      rgb(\"Orchid\"), true,\n",
    "      rgb(\"DarkSalmon\"), false));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "0x000000: Black\n",
    "******************************\n",
    "0xFFFFFF: White\n",
    "******************************\n",
    "0x000000: Black\n",
    "0x000080: Navy\n",
    "0x00008B: DarkBlue\n",
    "0x0000CD: MediumBlue\n",
    "0x0000FF: Blue\n",
    "0x006400: DarkGreen\n",
    "0x008000: Green\n",
    "0x008080: Teal\n",
    "0x008B8B: DarkCyan\n",
    "0x00BFFF: DeepSkyBlue\n",
    "0x00CED1: DarkTurquoise\n",
    "0x00FA9A: MediumSpringGreen\n",
    "0x00FF00: Lime\n",
    "******************************\n",
    "0x00BFFF: DeepSkyBlue\n",
    "******************************\n",
    "0x008B8B: DarkCyan\n",
    "******************************\n",
    "0x00FF00: Lime\n",
    "0x00FA9A: MediumSpringGreen\n",
    "0x00CED1: DarkTurquoise\n",
    "0x00BFFF: DeepSkyBlue\n",
    "0x008B8B: DarkCyan\n",
    "0x008080: Teal\n",
    "0x008000: Green\n",
    "0x006400: DarkGreen\n",
    "0x0000FF: Blue\n",
    "0x0000CD: MediumBlue\n",
    "0x00008B: DarkBlue\n",
    "0x000080: Navy\n",
    "0x000000: Black\n",
    "******************************\n",
    "0xFFE4E1: MistyRose\n",
    "0xFFEBCD: BlanchedAlmond\n",
    "0xFFEFD5: PapayaWhip\n",
    "0xFFF0F5: LavenderBlush\n",
    "0xFFF5EE: SeaShell\n",
    "0xFFF8DC: Cornsilk\n",
    "0xFFFACD: LemonChiffon\n",
    "0xFFFAF0: FloralWhite\n",
    "0xFFFAFA: Snow\n",
    "0xFFFF00: Yellow\n",
    "0xFFFFE0: LightYellow\n",
    "0xFFFFF0: Ivory\n",
    "0xFFFFFF: White\n",
    "******************************\n",
    "0xDA70D6: Orchid\n",
    "0xDAA520: GoldenRod\n",
    "0xDB7093: PaleVioletRed\n",
    "0xDC143C: Crimson\n",
    "0xDCDCDC: Gainsboro\n",
    "0xDDA0DD: Plum\n",
    "0xDEB887: BurlyWood\n",
    "0xE0FFFF: LightCyan\n",
    "0xE6E6FA: Lavender\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在主方法中可以看到 **NavigableMap** 的各种功能。 因为 **NavigableMap** 具有键顺序，所以它使用了 `firstEntry()` 和 `lastEntry()` 的概念。调用 `headMap()` 会生成一个 **NavigableMap** ，其中包含了从 **Map** 的开头到 `headMap()` 参数中所指向的一组元素，其中 **boolean** 值指示结果中是否包含该参数。调用 `tailMap()` 执行了类似的操作，只不过是从参数开始到 **Map** 的末尾。 `subMap()` 则允许生成 **Map** 中间的一部分。\n",
    "\n",
    "`ceilingEntry()` 从当前键值对向上搜索下一个键值对，`floorEntry()` 则是向下搜索。 `descendingMap()` 反转了 **NavigableMap** 的顺序。\n",
    "\n",
    "如果需要通过分割 **Map** 来简化所正在解决的问题，则 **NavigableMap** 可以做到。具有类似的功能的其它集合实现也可以用来帮助解决问题。\n",
    "\n",
    "<!-- Filling Collections -->\n",
    "## 填充集合\n",
    "\n",
    "与 **Arrays** 一样，这里有一个名为 **Collections** 的伴随类（companion class），包含了一些 **static** 的实用方法，其中包括一个名为 `fill()` 的方法。 `fill()` 只复制整个集合中的单个对象引用。此外，它仅适用于 **List** 对象，但结果列表可以传递给构造方法或 `addAll()` 方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/FillingLists.java\n",
    "// Collections.fill() & Collections.nCopies()\n",
    "import java.util.*;\n",
    "\n",
    "class StringAddress {\n",
    "  private String s;\n",
    "  StringAddress(String s) { this.s = s; }\n",
    "  @Override\n",
    "  public String toString() {\n",
    "    return super.toString() + \" \" + s;\n",
    "  }\n",
    "}\n",
    "\n",
    "public class FillingLists {\n",
    "  public static void main(String[] args) {\n",
    "    List<StringAddress> list = new ArrayList<>(\n",
    "      Collections.nCopies(4,\n",
    "        new StringAddress(\"Hello\")));\n",
    "    System.out.println(list);\n",
    "    Collections.fill(list,\n",
    "      new StringAddress(\"World!\"));\n",
    "    System.out.println(list);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[StringAddress@15db9742 Hello, StringAddress@15db9742\n",
    "Hello, StringAddress@15db9742 Hello,\n",
    "StringAddress@15db9742 Hello]\n",
    "[StringAddress@6d06d69c World!, StringAddress@6d06d69c\n",
    "World!, StringAddress@6d06d69c World!,\n",
    "StringAddress@6d06d69c World!]\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个示例展示了两种使用对单个对象的引用来填充 **Collection** 的方法。 第一个： `Collections.nCopies()` ，创建一个 **List**，并传递给 **ArrayList** 的构造方法，进而填充了 **ArrayList** 。\n",
    "\n",
    "**StringAddress** 中的 `toString()` 方法调用了 `Object.toString()` ，它先生成类名，后跟着对象的哈希码的无符号十六进制表示（哈希吗由 `hashCode()` 方法生成）。 输出显示所有的引用都指向同一个对象。调用第二个方法 `Collections.fill()` 后也是如此。 `fill()` 方法的用处非常有限，它只能替换 **List** 中已有的元素,而且不会添加新元素，\n",
    "\n",
    "### 使用 Suppliers 填充集合\n",
    "\n",
    "[第二十章 泛型]()章节中介绍的 **onjava.Suppliers** 类为填充集合提供了通用解决方案。 这是一个使用 **Suppliers** 初始化几种不同类型的 **Collection** 的示例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/SuppliersCollectionTest.java\n",
    "import java.util.*;\n",
    "import java.util.function.*;\n",
    "import java.util.stream.*;\n",
    "import onjava.*;\n",
    "\n",
    "class Government implements Supplier<String> {\n",
    "  static String[] foundation = (\n",
    "    \"strange women lying in ponds \" +\n",
    "    \"distributing swords is no basis \" +\n",
    "    \"for a system of government\").split(\" \");\n",
    "  private int index;\n",
    "  @Override\n",
    "  public String get() {\n",
    "    return foundation[index++];\n",
    "  }\n",
    "}\n",
    "\n",
    "public class SuppliersCollectionTest {\n",
    "  public static void main(String[] args) {\n",
    "    // Suppliers class from the Generics chapter:\n",
    "    Set<String> set = Suppliers.create(\n",
    "      LinkedHashSet::new, new Government(), 15);\n",
    "    System.out.println(set);\n",
    "    List<String> list = Suppliers.create(\n",
    "      LinkedList::new, new Government(), 15);\n",
    "    System.out.println(list);\n",
    "    list = new ArrayList<>();\n",
    "    Suppliers.fill(list, new Government(), 15);\n",
    "    System.out.println(list);\n",
    "\n",
    "    // Or we can use Streams:\n",
    "    set = Arrays.stream(Government.foundation)\n",
    "      .collect(Collectors.toSet());\n",
    "    System.out.println(set);\n",
    "    list = Arrays.stream(Government.foundation)\n",
    "      .collect(Collectors.toList());\n",
    "    System.out.println(list);\n",
    "    list = Arrays.stream(Government.foundation)\n",
    "      .collect(Collectors\n",
    "        .toCollection(LinkedList::new));\n",
    "    System.out.println(list);\n",
    "    set = Arrays.stream(Government.foundation)\n",
    "      .collect(Collectors\n",
    "        .toCollection(LinkedHashSet::new));\n",
    "    System.out.println(set);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[strange, women, lying, in, ponds, distributing,\n",
    "swords, is, no, basis, for, a, system, of, government]\n",
    "[strange, women, lying, in, ponds, distributing,\n",
    "swords, is, no, basis, for, a, system, of, government]\n",
    "[strange, women, lying, in, ponds, distributing,\n",
    "swords, is, no, basis, for, a, system, of, government]\n",
    "[ponds, no, a, in, swords, for, is, basis, strange,\n",
    "system, government, distributing, of, women, lying]\n",
    "[strange, women, lying, in, ponds, distributing,\n",
    "swords, is, no, basis, for, a, system, of, government]\n",
    "[strange, women, lying, in, ponds, distributing,\n",
    "swords, is, no, basis, for, a, system, of, government]\n",
    "[strange, women, lying, in, ponds, distributing,\n",
    "swords, is, no, basis, for, a, system, of, government]\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**LinkedHashSet** 中的的元素按插入顺序排列，因为它维护一个链表来保存该顺序。\n",
    "\n",
    "但是请注意示例的第二部分：大多数情况下都可以使用 **Stream** 来创建和填充 **Collection** 。在本例中的 **Stream** 版本不需要声明 **Supplier** 所想要创建的元素数量;，它直接吸收了 **Stream** 中的所有元素。\n",
    "\n",
    "尽可能优先选择 **Stream** 来解决问题。\n",
    "\n",
    "### Map Suppliers\n",
    "\n",
    "使用 **Supplier** 来填充 **Map** 时需要一个 **Pair** 类，因为每次调用一个 **Supplier** 的 `get()` 方法时，都必须生成一对对象（一个键和一个值）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// onjava/Pair.java\n",
    "package onjava;\n",
    "\n",
    "public class Pair<K, V> {\n",
    "  public final K key;\n",
    "  public final V value;\n",
    "  public Pair(K k, V v) {\n",
    "    key = k;\n",
    "    value = v;\n",
    "  }\n",
    "  public K key() { return key; }\n",
    "  public V value() { return value; }\n",
    "  public static <K,V> Pair<K, V> make(K k, V v) {\n",
    "    return new Pair<K,V>(k, v);\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Pair** 是一个只读的 *数据传输对象* （Data Transfer Object）或 *信使* （Messenger）。 这与[第二十章 泛型]()章节中的 **Tuple2** 基本相同，但名字更适合 **Map** 初始化。我还添加了静态的 `make()` 方法，以便为创建 **Pair** 对象提供一个更简洁的名字。\n",
    "\n",
    "Java 8 的 **Stream** 提供了填充 **Map** 的便捷方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/StreamFillMaps.java\n",
    "import java.util.*;\n",
    "import java.util.function.*;\n",
    "import java.util.stream.*;\n",
    "import onjava.*;\n",
    "\n",
    "class Letters\n",
    "implements Supplier<Pair<Integer,String>> {\n",
    "  private int number = 1;\n",
    "  private char letter = 'A';\n",
    "  @Override\n",
    "  public Pair<Integer,String> get() {\n",
    "    return new Pair<>(number++, \"\" + letter++);\n",
    "  }\n",
    "}\n",
    "\n",
    "public class StreamFillMaps {\n",
    "  public static void main(String[] args) {\n",
    "    Map<Integer,String> m =\n",
    "      Stream.generate(new Letters())\n",
    "      .limit(11)\n",
    "      .collect(Collectors\n",
    "        .toMap(Pair::key, Pair::value));\n",
    "    System.out.println(m);\n",
    "\n",
    "    // Two separate Suppliers:\n",
    "    Rand.String rs = new Rand.String(3);\n",
    "    Count.Character cc = new Count.Character();\n",
    "    Map<Character,String> mcs = Stream.generate(\n",
    "      () -> Pair.make(cc.get(), rs.get()))\n",
    "      .limit(8)\n",
    "      .collect(Collectors\n",
    "        .toMap(Pair::key, Pair::value));\n",
    "    System.out.println(mcs);\n",
    "\n",
    "    // A key Supplier and a single value:\n",
    "    Map<Character,String> mcs2 = Stream.generate(\n",
    "      () -> Pair.make(cc.get(), \"Val\"))\n",
    "      .limit(8)\n",
    "      .collect(Collectors\n",
    "        .toMap(Pair::key, Pair::value));\n",
    "    System.out.println(mcs2);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "{1=A, 2=B, 3=C, 4=D, 5=E, 6=F, 7=G, 8=H, 9=I, 10=J,\n",
    "11=K}\n",
    "{b=btp, c=enp, d=ccu, e=xsz, f=gvg, g=mei, h=nne,\n",
    "i=elo}\n",
    "{p=Val, q=Val, j=Val, k=Val, l=Val, m=Val, n=Val,\n",
    "o=Val}\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的示例中出现了一个模式，可以使用它来创建一个自动创建和填充 **Map** 的工具："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// onjava/FillMap.java\n",
    "package onjava;\n",
    "import java.util.*;\n",
    "import java.util.function.*;\n",
    "import java.util.stream.*;\n",
    "\n",
    "public class FillMap {\n",
    "  public static <K, V> Map<K,V>\n",
    "  basic(Supplier<Pair<K,V>> pairGen, int size) {\n",
    "    return Stream.generate(pairGen)\n",
    "      .limit(size)\n",
    "      .collect(Collectors\n",
    "        .toMap(Pair::key, Pair::value));\n",
    "  }\n",
    "  public static <K, V> Map<K,V>\n",
    "  basic(Supplier<K> keyGen,\n",
    "        Supplier<V> valueGen, int size) {\n",
    "    return Stream.generate(\n",
    "      () -> Pair.make(keyGen.get(), valueGen.get()))\n",
    "      .limit(size)\n",
    "      .collect(Collectors\n",
    "        .toMap(Pair::key, Pair::value));\n",
    "  }\n",
    "  public static <K, V, M extends Map<K,V>>\n",
    "  M create(Supplier<K> keyGen,\n",
    "           Supplier<V> valueGen,\n",
    "           Supplier<M> mapSupplier, int size) {\n",
    "    return Stream.generate( () ->\n",
    "      Pair.make(keyGen.get(), valueGen.get()))\n",
    "        .limit(size)\n",
    "        .collect(Collectors\n",
    "          .toMap(Pair::key, Pair::value,\n",
    "                 (k, v) -> k, mapSupplier));\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "basic() 方法生成一个默认的 **Map** ，而 `create()` 方法允许指定一个确切的 **Map** 类型，并返回那个确切的类型。\n",
    "\n",
    "下面是一个测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/FillMapTest.java\n",
    "import java.util.*;\n",
    "import java.util.function.*;\n",
    "import java.util.stream.*;\n",
    "import onjava.*;\n",
    "\n",
    "public class FillMapTest {\n",
    "  public static void main(String[] args) {\n",
    "    Map<String,Integer> mcs = FillMap.basic(\n",
    "      new Rand.String(4), new Count.Integer(), 7);\n",
    "    System.out.println(mcs);\n",
    "    HashMap<String,Integer> hashm =\n",
    "      FillMap.create(new Rand.String(4),\n",
    "        new Count.Integer(), HashMap::new, 7);\n",
    "    System.out.println(hashm);\n",
    "    LinkedHashMap<String,Integer> linkm =\n",
    "      FillMap.create(new Rand.String(4),\n",
    "        new Count.Integer(), LinkedHashMap::new, 7);\n",
    "    System.out.println(linkm);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "{npcc=1, ztdv=6, gvgm=3, btpe=0, einn=4, eelo=5,\n",
    "uxsz=2}\n",
    "{npcc=1, ztdv=6, gvgm=3, btpe=0, einn=4, eelo=5,\n",
    "uxsz=2}\n",
    "{btpe=0, npcc=1, uxsz=2, gvgm=3, einn=4, eelo=5,\n",
    "ztdv=6}\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- Custom Collection and Map using Flyweight -->\n",
    "## 使用享元（Flyweight）自定义Collection和Map\n",
    "\n",
    "本节介绍如何创建自定义 **Collection** 和 **Map** 实现。每个 **java.util** 中的集合都有自己的 **Abstract** 类，它提供了该集合的部分实现，因此只需要实现必要的方法来生成所需的集合。你将看到通过继承 **java.util.Abstract** 类来创建自定义 **Map** 和 **Collection** 是多么简单。例如，要创建一个只读的 **Set** ，则可以从 **AbstractSet** 继承并实现 `iterator()` 和 `size()` 。最后一个示例是生成测试数据的另一种方法。生成的集合通常是只读的，并且所提供的方法最少。\n",
    "\n",
    "该解决方案还演示了 *享元* （Flyweight）设计模式。当普通解决方案需要太多对象时，或者当生成普通对象占用太多空间时，可以使用享元。享元设计模式将对象的一部分外部化（externalizes）。相比于把对象的所有内容都包含在对象中，这样做使得对象的部分或者全部可以在更有效的外部表中查找，或通过一些节省空间的其他计算生成。\n",
    "\n",
    "下面是一个可以是任何大小的 **List** ，并且（有效地）使用 **Integer** 数据进行预初始化。要从 **AbstractList** 创建只读 **List** ，必须实现 `get()` 和 `size()`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// onjava/CountingIntegerList.java\n",
    "// List of any length, containing sample data\n",
    "// {java onjava.CountingIntegerList}\n",
    "package onjava;\n",
    "import java.util.*;\n",
    "\n",
    "public class CountingIntegerList\n",
    "extends AbstractList<Integer> {\n",
    "  private int size;\n",
    "  public CountingIntegerList() { size = 0; }\n",
    "  public CountingIntegerList(int size) {\n",
    "    this.size = size < 0 ? 0 : size;\n",
    "  }\n",
    "  @Override\n",
    "  public Integer get(int index) {\n",
    "    return index;\n",
    "  }\n",
    "  @Override\n",
    "  public int size() { return size; }\n",
    "  public static void main(String[] args) {\n",
    "    List<Integer> cil =\n",
    "      new CountingIntegerList(30);\n",
    "    System.out.println(cil);\n",
    "    System.out.println(cil.get(500));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,\n",
    "16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]\n",
    "500\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "只有当想要限制 **List** 的长度时， **size** 值才是重要的，就像在主方法中那样。即使在这种情况下， `get()` 也会产生任何值。\n",
    "\n",
    "这个类是享元模式的一个简洁的例子。当需要的时候， `get()` “计算”所需的值，因此没必要存储和初始化实际的底层 **List** 结构。\n",
    "\n",
    "在大多数程序中，这里所保存的存储结构永远都不会改变。但是，它允许用非常大的 **index** 来调用 `List.get()` ，而 **List** 并不需要填充到这么大。此外，还可以在程序中大量使用 **CountingIntegerLists** 而无需担心存储问题。实际上，享元的一个好处是它允许使用更好的抽象而不用担心资源。\n",
    "\n",
    "可以使用享元设计模式来实现具有任何大小数据集的其他“初始化”自定义集合。下面是一个 **Map** ，它为每一个 **Integer** 键产生唯一的值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// onjava/CountMap.java\n",
    "// Unlimited-length Map containing sample data\n",
    "// {java onjava.CountMap}\n",
    "package onjava;\n",
    "import java.util.*;\n",
    "import java.util.stream.*;\n",
    "\n",
    "public class CountMap\n",
    "extends AbstractMap<Integer,String> {\n",
    "  private int size;\n",
    "  private static char[] chars =\n",
    "    \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\".toCharArray();\n",
    "  private static String value(int key) {\n",
    "    return\n",
    "      chars[key % chars.length] +\n",
    "      Integer.toString(key / chars.length);\n",
    "  }\n",
    "  public CountMap(int size) {\n",
    "    this.size = size < 0 ? 0 : size;\n",
    "  }\n",
    "  @Override\n",
    "  public String get(Object key) {\n",
    "    return value((Integer)key);\n",
    "  }\n",
    "  private static class Entry\n",
    "  implements Map.Entry<Integer,String> {\n",
    "    int index;\n",
    "    Entry(int index) { this.index = index; }\n",
    "    @Override\n",
    "    public boolean equals(Object o) {\n",
    "      return o instanceof Entry &&\n",
    "        Objects.equals(index, ((Entry)o).index);\n",
    "    }\n",
    "    @Override\n",
    "    public Integer getKey() { return index; }\n",
    "    @Override\n",
    "    public String getValue() {\n",
    "      return value(index);\n",
    "    }\n",
    "    @Override\n",
    "    public String setValue(String value) {\n",
    "      throw new UnsupportedOperationException();\n",
    "    }\n",
    "    @Override\n",
    "    public int hashCode() {\n",
    "      return Objects.hashCode(index);\n",
    "    }\n",
    "  }\n",
    "  @Override\n",
    "  public Set<Map.Entry<Integer,String>> entrySet() {\n",
    "    // LinkedHashSet retains initialization order:\n",
    "    return IntStream.range(0, size)\n",
    "      .mapToObj(Entry::new)\n",
    "      .collect(Collectors\n",
    "        .toCollection(LinkedHashSet::new));\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    final int size = 6;\n",
    "    CountMap cm = new CountMap(60);\n",
    "    System.out.println(cm);\n",
    "    System.out.println(cm.get(500));\n",
    "    cm.values().stream()\n",
    "      .limit(size)\n",
    "      .forEach(System.out::println);\n",
    "    System.out.println();\n",
    "    new Random(47).ints(size, 0, 1000)\n",
    "      .mapToObj(cm::get)\n",
    "      .forEach(System.out::println);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0,\n",
    "9=J0, 10=K0, 11=L0, 12=M0, 13=N0, 14=O0, 15=P0, 16=Q0,\n",
    "17=R0, 18=S0, 19=T0, 20=U0, 21=V0, 22=W0, 23=X0, 24=Y0,\n",
    "25=Z0, 26=A1, 27=B1, 28=C1, 29=D1, 30=E1, 31=F1, 32=G1,\n",
    "33=H1, 34=I1, 35=J1, 36=K1, 37=L1, 38=M1, 39=N1, 40=O1,\n",
    "41=P1, 42=Q1, 43=R1, 44=S1, 45=T1, 46=U1, 47=V1, 48=W1,\n",
    "49=X1, 50=Y1, 51=Z1, 52=A2, 53=B2, 54=C2, 55=D2, 56=E2,\n",
    "57=F2, 58=G2, 59=H2}\n",
    "G19\n",
    "A0\n",
    "B0\n",
    "C0\n",
    "D0\n",
    "E0\n",
    "F0\n",
    "\n",
    "Y9\n",
    "J21\n",
    "R26\n",
    "D33\n",
    "Z36\n",
    "N16\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "要创建一个只读的 **Map** ，则从 **AbstractMap** 继承并实现 `entrySet()` 。私有的 `value()` 方法计算任何键的值，并在 `get()` 和 `Entry.getValue()` 中使用。可以忽略 **CountMap** 的大小。\n",
    "\n",
    "这里是使用了 **LinkedHashSet** 而不是创建自定义 **Set** 类，因此并未完全实现享元。只有在调用 `entrySet()` 时才会生成此对象。\n",
    "\n",
    "现在创建一个更复杂的享元。这个示例中的数据集是世界各国及其首都的 **Map** 。 `capitals()` 方法生成一个国家和首都的 **Map** 。 `names()` 方法生成一个由国家名字组成的 **List** 。 当给定了表示所需大小的 **int** 参数时，两种方法都生成对应大小的列表片段："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// onjava/Countries.java\n",
    "// \"Flyweight\" Maps and Lists of sample data\n",
    "// {java onjava.Countries}\n",
    "package onjava;\n",
    "import java.util.*;\n",
    "\n",
    "public class Countries {\n",
    "  public static final String[][] DATA = {\n",
    "    // Africa\n",
    "    {\"ALGERIA\",\"Algiers\"},\n",
    "    {\"ANGOLA\",\"Luanda\"},\n",
    "    {\"BENIN\",\"Porto-Novo\"},\n",
    "    {\"BOTSWANA\",\"Gaberone\"},\n",
    "    {\"BURKINA FASO\",\"Ouagadougou\"},\n",
    "    {\"BURUNDI\",\"Bujumbura\"},\n",
    "    {\"CAMEROON\",\"Yaounde\"},\n",
    "    {\"CAPE VERDE\",\"Praia\"},\n",
    "    {\"CENTRAL AFRICAN REPUBLIC\",\"Bangui\"},\n",
    "    {\"CHAD\",\"N'djamena\"},\n",
    "    {\"COMOROS\",\"Moroni\"},\n",
    "    {\"CONGO\",\"Brazzaville\"},\n",
    "    {\"DJIBOUTI\",\"Dijibouti\"},\n",
    "    {\"EGYPT\",\"Cairo\"},\n",
    "    {\"EQUATORIAL GUINEA\",\"Malabo\"},\n",
    "    {\"ERITREA\",\"Asmara\"},\n",
    "    {\"ETHIOPIA\",\"Addis Ababa\"},\n",
    "    {\"GABON\",\"Libreville\"},\n",
    "    {\"THE GAMBIA\",\"Banjul\"},\n",
    "    {\"GHANA\",\"Accra\"},\n",
    "    {\"GUINEA\",\"Conakry\"},\n",
    "    {\"BISSAU\",\"Bissau\"},\n",
    "    {\"COTE D'IVOIR (IVORY COAST)\",\"Yamoussoukro\"},\n",
    "    {\"KENYA\",\"Nairobi\"},\n",
    "    {\"LESOTHO\",\"Maseru\"},\n",
    "    {\"LIBERIA\",\"Monrovia\"},\n",
    "    {\"LIBYA\",\"Tripoli\"},\n",
    "    {\"MADAGASCAR\",\"Antananarivo\"},\n",
    "    {\"MALAWI\",\"Lilongwe\"},\n",
    "    {\"MALI\",\"Bamako\"},\n",
    "    {\"MAURITANIA\",\"Nouakchott\"},\n",
    "    {\"MAURITIUS\",\"Port Louis\"},\n",
    "    {\"MOROCCO\",\"Rabat\"},\n",
    "    {\"MOZAMBIQUE\",\"Maputo\"},\n",
    "    {\"NAMIBIA\",\"Windhoek\"},\n",
    "    {\"NIGER\",\"Niamey\"},\n",
    "    {\"NIGERIA\",\"Abuja\"},\n",
    "    {\"RWANDA\",\"Kigali\"},\n",
    "    {\"SAO TOME E PRINCIPE\",\"Sao Tome\"},\n",
    "    {\"SENEGAL\",\"Dakar\"},\n",
    "    {\"SEYCHELLES\",\"Victoria\"},\n",
    "    {\"SIERRA LEONE\",\"Freetown\"},\n",
    "    {\"SOMALIA\",\"Mogadishu\"},\n",
    "    {\"SOUTH AFRICA\",\"Pretoria/Cape Town\"},\n",
    "    {\"SUDAN\",\"Khartoum\"},\n",
    "    {\"SWAZILAND\",\"Mbabane\"},\n",
    "    {\"TANZANIA\",\"Dodoma\"},\n",
    "    {\"TOGO\",\"Lome\"},\n",
    "    {\"TUNISIA\",\"Tunis\"},\n",
    "    {\"UGANDA\",\"Kampala\"},\n",
    "    {\"DEMOCRATIC REPUBLIC OF THE CONGO (ZAIRE)\",\n",
    "     \"Kinshasa\"},\n",
    "    {\"ZAMBIA\",\"Lusaka\"},\n",
    "    {\"ZIMBABWE\",\"Harare\"},\n",
    "    // Asia\n",
    "    {\"AFGHANISTAN\",\"Kabul\"},\n",
    "    {\"BAHRAIN\",\"Manama\"},\n",
    "    {\"BANGLADESH\",\"Dhaka\"},\n",
    "    {\"BHUTAN\",\"Thimphu\"},\n",
    "    {\"BRUNEI\",\"Bandar Seri Begawan\"},\n",
    "    {\"CAMBODIA\",\"Phnom Penh\"},\n",
    "    {\"CHINA\",\"Beijing\"},\n",
    "    {\"CYPRUS\",\"Nicosia\"},\n",
    "    {\"INDIA\",\"New Delhi\"},\n",
    "    {\"INDONESIA\",\"Jakarta\"},\n",
    "    {\"IRAN\",\"Tehran\"},\n",
    "    {\"IRAQ\",\"Baghdad\"},\n",
    "    {\"ISRAEL\",\"Jerusalem\"},\n",
    "    {\"JAPAN\",\"Tokyo\"},\n",
    "    {\"JORDAN\",\"Amman\"},\n",
    "    {\"KUWAIT\",\"Kuwait City\"},\n",
    "    {\"LAOS\",\"Vientiane\"},\n",
    "    {\"LEBANON\",\"Beirut\"},\n",
    "    {\"MALAYSIA\",\"Kuala Lumpur\"},\n",
    "    {\"THE MALDIVES\",\"Male\"},\n",
    "    {\"MONGOLIA\",\"Ulan Bator\"},\n",
    "    {\"MYANMAR (BURMA)\",\"Rangoon\"},\n",
    "    {\"NEPAL\",\"Katmandu\"},\n",
    "    {\"NORTH KOREA\",\"P'yongyang\"},\n",
    "    {\"OMAN\",\"Muscat\"},\n",
    "    {\"PAKISTAN\",\"Islamabad\"},\n",
    "    {\"PHILIPPINES\",\"Manila\"},\n",
    "    {\"QATAR\",\"Doha\"},\n",
    "    {\"SAUDI ARABIA\",\"Riyadh\"},\n",
    "    {\"SINGAPORE\",\"Singapore\"},\n",
    "    {\"SOUTH KOREA\",\"Seoul\"},\n",
    "    {\"SRI LANKA\",\"Colombo\"},\n",
    "    {\"SYRIA\",\"Damascus\"},\n",
    "    {\"TAIWAN (REPUBLIC OF CHINA)\",\"Taipei\"},\n",
    "    {\"THAILAND\",\"Bangkok\"},\n",
    "    {\"TURKEY\",\"Ankara\"},\n",
    "    {\"UNITED ARAB EMIRATES\",\"Abu Dhabi\"},\n",
    "    {\"VIETNAM\",\"Hanoi\"},\n",
    "    {\"YEMEN\",\"Sana'a\"},\n",
    "    // Australia and Oceania\n",
    "    {\"AUSTRALIA\",\"Canberra\"},\n",
    "    {\"FIJI\",\"Suva\"},\n",
    "    {\"KIRIBATI\",\"Bairiki\"},\n",
    "    {\"MARSHALL ISLANDS\",\"Dalap-Uliga-Darrit\"},\n",
    "    {\"MICRONESIA\",\"Palikir\"},\n",
    "    {\"NAURU\",\"Yaren\"},\n",
    "    {\"NEW ZEALAND\",\"Wellington\"},\n",
    "    {\"PALAU\",\"Koror\"},\n",
    "    {\"PAPUA NEW GUINEA\",\"Port Moresby\"},\n",
    "    {\"SOLOMON ISLANDS\",\"Honaira\"},\n",
    "    {\"TONGA\",\"Nuku'alofa\"},\n",
    "    {\"TUVALU\",\"Fongafale\"},\n",
    "    {\"VANUATU\",\"Port Vila\"},\n",
    "    {\"WESTERN SAMOA\",\"Apia\"},\n",
    "    // Eastern Europe and former USSR\n",
    "    {\"ARMENIA\",\"Yerevan\"},\n",
    "    {\"AZERBAIJAN\",\"Baku\"},\n",
    "    {\"BELARUS (BYELORUSSIA)\",\"Minsk\"},\n",
    "    {\"BULGARIA\",\"Sofia\"},\n",
    "    {\"GEORGIA\",\"Tbilisi\"},\n",
    "    {\"KAZAKSTAN\",\"Almaty\"},\n",
    "    {\"KYRGYZSTAN\",\"Alma-Ata\"},\n",
    "    {\"MOLDOVA\",\"Chisinau\"},\n",
    "    {\"RUSSIA\",\"Moscow\"},\n",
    "    {\"TAJIKISTAN\",\"Dushanbe\"},\n",
    "    {\"TURKMENISTAN\",\"Ashkabad\"},\n",
    "    {\"UKRAINE\",\"Kyiv\"},\n",
    "    {\"UZBEKISTAN\",\"Tashkent\"},\n",
    "    // Europe\n",
    "    {\"ALBANIA\",\"Tirana\"},\n",
    "    {\"ANDORRA\",\"Andorra la Vella\"},\n",
    "    {\"AUSTRIA\",\"Vienna\"},\n",
    "    {\"BELGIUM\",\"Brussels\"},\n",
    "    {\"BOSNIA-HERZEGOVINA\",\"Sarajevo\"},\n",
    "    {\"CROATIA\",\"Zagreb\"},\n",
    "    {\"CZECH REPUBLIC\",\"Prague\"},\n",
    "    {\"DENMARK\",\"Copenhagen\"},\n",
    "    {\"ESTONIA\",\"Tallinn\"},\n",
    "    {\"FINLAND\",\"Helsinki\"},\n",
    "    {\"FRANCE\",\"Paris\"},\n",
    "    {\"GERMANY\",\"Berlin\"},\n",
    "    {\"GREECE\",\"Athens\"},\n",
    "    {\"HUNGARY\",\"Budapest\"},\n",
    "    {\"ICELAND\",\"Reykjavik\"},\n",
    "    {\"IRELAND\",\"Dublin\"},\n",
    "    {\"ITALY\",\"Rome\"},\n",
    "    {\"LATVIA\",\"Riga\"},\n",
    "    {\"LIECHTENSTEIN\",\"Vaduz\"},\n",
    "    {\"LITHUANIA\",\"Vilnius\"},\n",
    "    {\"LUXEMBOURG\",\"Luxembourg\"},\n",
    "    {\"MACEDONIA\",\"Skopje\"},\n",
    "    {\"MALTA\",\"Valletta\"},\n",
    "    {\"MONACO\",\"Monaco\"},\n",
    "    {\"MONTENEGRO\",\"Podgorica\"},\n",
    "    {\"THE NETHERLANDS\",\"Amsterdam\"},\n",
    "    {\"NORWAY\",\"Oslo\"},\n",
    "    {\"POLAND\",\"Warsaw\"},\n",
    "    {\"PORTUGAL\",\"Lisbon\"},\n",
    "    {\"ROMANIA\",\"Bucharest\"},\n",
    "    {\"SAN MARINO\",\"San Marino\"},\n",
    "    {\"SERBIA\",\"Belgrade\"},\n",
    "    {\"SLOVAKIA\",\"Bratislava\"},\n",
    "    {\"SLOVENIA\",\"Ljuijana\"},\n",
    "    {\"SPAIN\",\"Madrid\"},\n",
    "    {\"SWEDEN\",\"Stockholm\"},\n",
    "    {\"SWITZERLAND\",\"Berne\"},\n",
    "    {\"UNITED KINGDOM\",\"London\"},\n",
    "    {\"VATICAN CITY\",\"Vatican City\"},\n",
    "    // North and Central America\n",
    "    {\"ANTIGUA AND BARBUDA\",\"Saint John's\"},\n",
    "    {\"BAHAMAS\",\"Nassau\"},\n",
    "    {\"BARBADOS\",\"Bridgetown\"},\n",
    "    {\"BELIZE\",\"Belmopan\"},\n",
    "    {\"CANADA\",\"Ottawa\"},\n",
    "    {\"COSTA RICA\",\"San Jose\"},\n",
    "    {\"CUBA\",\"Havana\"},\n",
    "    {\"DOMINICA\",\"Roseau\"},\n",
    "    {\"DOMINICAN REPUBLIC\",\"Santo Domingo\"},\n",
    "    {\"EL SALVADOR\",\"San Salvador\"},\n",
    "    {\"GRENADA\",\"Saint George's\"},\n",
    "    {\"GUATEMALA\",\"Guatemala City\"},\n",
    "    {\"HAITI\",\"Port-au-Prince\"},\n",
    "    {\"HONDURAS\",\"Tegucigalpa\"},\n",
    "    {\"JAMAICA\",\"Kingston\"},\n",
    "    {\"MEXICO\",\"Mexico City\"},\n",
    "    {\"NICARAGUA\",\"Managua\"},\n",
    "    {\"PANAMA\",\"Panama City\"},\n",
    "    {\"ST. KITTS AND NEVIS\",\"Basseterre\"},\n",
    "    {\"ST. LUCIA\",\"Castries\"},\n",
    "    {\"ST. VINCENT AND THE GRENADINES\",\"Kingstown\"},\n",
    "    {\"UNITED STATES OF AMERICA\",\"Washington, D.C.\"},\n",
    "    // South America\n",
    "    {\"ARGENTINA\",\"Buenos Aires\"},\n",
    "    {\"BOLIVIA\",\"Sucre (legal)/La Paz(administrative)\"},\n",
    "    {\"BRAZIL\",\"Brasilia\"},\n",
    "    {\"CHILE\",\"Santiago\"},\n",
    "    {\"COLOMBIA\",\"Bogota\"},\n",
    "    {\"ECUADOR\",\"Quito\"},\n",
    "    {\"GUYANA\",\"Georgetown\"},\n",
    "    {\"PARAGUAY\",\"Asuncion\"},\n",
    "    {\"PERU\",\"Lima\"},\n",
    "    {\"SURINAME\",\"Paramaribo\"},\n",
    "    {\"TRINIDAD AND TOBAGO\",\"Port of Spain\"},\n",
    "    {\"URUGUAY\",\"Montevideo\"},\n",
    "    {\"VENEZUELA\",\"Caracas\"},\n",
    "  };\n",
    "  // Use AbstractMap by implementing entrySet()\n",
    "  private static class FlyweightMap\n",
    "  extends AbstractMap<String,String> {\n",
    "    private static class Entry\n",
    "    implements Map.Entry<String,String> {\n",
    "      int index;\n",
    "      Entry(int index) { this.index = index; }\n",
    "      @Override\n",
    "      public boolean equals(Object o) {\n",
    "        return o instanceof FlyweightMap &&\n",
    "          Objects.equals(DATA[index][0], o);\n",
    "      }\n",
    "      @Override\n",
    "      public int hashCode() {\n",
    "        return Objects.hashCode(DATA[index][0]);\n",
    "      }\n",
    "      @Override\n",
    "      public String getKey() { return DATA[index][0]; }\n",
    "      @Override\n",
    "      public String getValue() {\n",
    "        return DATA[index][1];\n",
    "      }\n",
    "      @Override\n",
    "      public String setValue(String value) {\n",
    "        throw new UnsupportedOperationException();\n",
    "      }\n",
    "    }\n",
    "    // Implement size() & iterator() for AbstractSet:\n",
    "    static class EntrySet\n",
    "    extends AbstractSet<Map.Entry<String,String>> {\n",
    "      private int size;\n",
    "      EntrySet(int size) {\n",
    "        if(size < 0)\n",
    "          this.size = 0;\n",
    "        // Can't be any bigger than the array:\n",
    "        else if(size > DATA.length)\n",
    "          this.size = DATA.length;\n",
    "        else\n",
    "          this.size = size;\n",
    "      }\n",
    "      @Override\n",
    "      public int size() { return size; }\n",
    "      private class Iter\n",
    "      implements Iterator<Map.Entry<String,String>> {\n",
    "        // Only one Entry object per Iterator:\n",
    "        private Entry entry = new Entry(-1);\n",
    "        @Override\n",
    "        public boolean hasNext() {\n",
    "          return entry.index < size - 1;\n",
    "        }\n",
    "        @Override\n",
    "        public Map.Entry<String,String> next() {\n",
    "          entry.index++;\n",
    "          return entry;\n",
    "        }\n",
    "        @Override\n",
    "        public void remove() {\n",
    "          throw new UnsupportedOperationException();\n",
    "        }\n",
    "      }\n",
    "      @Override\n",
    "      public\n",
    "      Iterator<Map.Entry<String,String>> iterator() {\n",
    "        return new Iter();\n",
    "      }\n",
    "    }\n",
    "    private static\n",
    "    Set<Map.Entry<String,String>> entries =\n",
    "      new EntrySet(DATA.length);\n",
    "    @Override\n",
    "    public Set<Map.Entry<String,String>> entrySet() {\n",
    "      return entries;\n",
    "    }\n",
    "  }\n",
    "  // Create a partial map of 'size' countries:\n",
    "  static Map<String,String> select(final int size) {\n",
    "    return new FlyweightMap() {\n",
    "      @Override\n",
    "      public Set<Map.Entry<String,String>> entrySet() {\n",
    "        return new EntrySet(size);\n",
    "      }\n",
    "    };\n",
    "  }\n",
    "  static Map<String,String> map = new FlyweightMap();\n",
    "  public static Map<String,String> capitals() {\n",
    "    return map; // The entire map\n",
    "  }\n",
    "  public static Map<String,String> capitals(int size) {\n",
    "    return select(size); // A partial map\n",
    "  }\n",
    "  static List<String> names =\n",
    "    new ArrayList<>(map.keySet());\n",
    "  // All the names:\n",
    "  public static List<String> names() { return names; }\n",
    "  // A partial list:\n",
    "  public static List<String> names(int size) {\n",
    "    return new ArrayList<>(select(size).keySet());\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    System.out.println(capitals(10));\n",
    "    System.out.println(names(10));\n",
    "    System.out.println(new HashMap<>(capitals(3)));\n",
    "    System.out.println(\n",
    "      new LinkedHashMap<>(capitals(3)));\n",
    "    System.out.println(new TreeMap<>(capitals(3)));\n",
    "    System.out.println(new Hashtable<>(capitals(3)));\n",
    "    System.out.println(new HashSet<>(names(6)));\n",
    "    System.out.println(new LinkedHashSet<>(names(6)));\n",
    "    System.out.println(new TreeSet<>(names(6)));\n",
    "    System.out.println(new ArrayList<>(names(6)));\n",
    "    System.out.println(new LinkedList<>(names(6)));\n",
    "    System.out.println(capitals().get(\"BRAZIL\"));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "{ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo,\n",
    "BOTSWANA=Gaberone, BURKINA FASO=Ouagadougou,\n",
    "BURUNDI=Bujumbura, CAMEROON=Yaounde, CAPE VERDE=Praia,\n",
    "CENTRAL AFRICAN REPUBLIC=Bangui, CHAD=N'djamena}\n",
    "[ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,\n",
    "BURUNDI, CAMEROON, CAPE VERDE, CENTRAL AFRICAN\n",
    "REPUBLIC, CHAD]\n",
    "{BENIN=Porto-Novo, ANGOLA=Luanda, ALGERIA=Algiers}\n",
    "{ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo}\n",
    "{ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo}\n",
    "{ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo}\n",
    "[BENIN, BOTSWANA, ANGOLA, BURKINA FASO, ALGERIA,\n",
    "BURUNDI]\n",
    "[ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,\n",
    "BURUNDI]\n",
    "[ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,\n",
    "BURUNDI]\n",
    "[ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,\n",
    "BURUNDI]\n",
    "[ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,\n",
    "BURUNDI]\n",
    "Brasilia\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二维数组 **String DATA** 是 **public** 的，因此可以在别处使用。 **FlyweightMap** 必须实现 `entrySet()` 方法，该方法需要一个自定义 **Set** 实现和一个自定义 **Map.Entry** 类。这是实现享元的另一种方法：每个 **Map.Entry** 对象存储它自身的索引，而不是实际的键和值。当调用 `getKey()` 或 `getValue()` 时，它使用索引返回相应的 **DATA** 元素。 **EntrySet** 确保它的 **size** 不大于 **DATA** 。\n",
    "\n",
    "享元的另一部分在 **EntrySet.Iterator** 中实现。相比于为 **DATA** 中的每个数据对创建一个 **Map.Entry** 对象，这里每个迭代器只有一个 **Map.Entry** 对象。 **Entry** 对象作为数据的窗口，它只包含 **String** 静态数组的索引。每次为迭代器调用 `next()` 时，**Entry** 中的索引都会递增，因此它会指向下一个数据对，然后从 `next()` 返回 **Iterators** 的单个 **Entry** 对象。[^1]\n",
    "\n",
    "`select()` 方法生成一个包含所需大小的 **EntrySet** 的 **FlyweightMap** ，这用于在主方法中演示的重载的 `capitals()` 和 `names()` 方法。\n",
    "\n",
    "<!-- Collection Functionality -->\n",
    "## 集合功能\n",
    "\n",
    "下面这个表格展示了可以对 **Collection** 执行的所有操作（不包括自动继承自 **Object** 的方法），因此，可以用 **List** ， **Set** ， **Queue** 或 **Deque** 执行这里的所有操作（这些接口可能也提供了一些其他的功能）。**Map** 不是从 **Collection** 继承的，所以要单独处理它。\n",
    "\n",
    "| 方法名 | 描述 |\n",
    "| :---: | :--- |\n",
    "| **boolean add(T)** | 确保集合包含该泛型类型 **T** 的参数。如果不添加参数，则返回 **false** 。 （这是一种“可选”方法，将在下一节中介绍。） |\n",
    "| **boolean addAll(Collection\\<? extends T\\>)** | 添加参数集合中的所有元素。只要有元素被成功添加则返回 **true**。（“可选的”） |\n",
    "| **void clear()** | 删除集合中的所有元素。（“可选的”） |\n",
    "| **boolean contains(T)** | 如果目标集合包含该泛型类型 **T** 的参数，则返回 **true** 。 |\n",
    "| **boolean containsAll(Collection\\<?\\>)** | 如果目标集合包含参数集合中的所有元素，则返回 **true** |\n",
    "| **boolean isEmpty()** | 如果集合为空，则返回 **true** |\n",
    "| **Iterator\\<T\\> iterator() Spliterator\\<T\\> spliterator()** | 返回一个迭代器来遍历集合中的元素。 **Spliterators** 更复杂一些，它用在并发场景 |\n",
    "| **boolean remove(Object)** | 如果目标集合包含该参数，则在集合中删除该参数，如果成功删除则返回 **true** 。（“可选的”） |\n",
    "| **boolean removeAll(Collection\\<?\\>)** | 删除目标集合中，参数集合所包含的全部元素。如果有元素被成功删除则返回 **true** 。 （“可选的”） |\n",
    "| **boolean removeIf(Predicate\\<? super E\\>)** | 删除此集合中，满足给定断言（predicate）的所有元素 |\n",
    "| **Stream\\<E\\> stream() Stream\\<E\\> parallelStream()** | 返回由该 **Collection** 中元素所组成的一个 **Stream** |\n",
    "| **int size()** | 返回集合中所包含元素的个数 |\n",
    "| **Object[] toArrat()** | 返回包含该集合所有元素的一个数组 |\n",
    "| **\\<T\\> T[] toArray(T[] a)** | 返回包含该集合所有元素的一个数组。结果的运行时类型是参数数组而不是普通的 **Object** 数组。 |\n",
    "\n",
    "这里没有提供用于随机访问元素的 **get()** 方法，因为 **Collection** 还包含 **Set** ，它维护自己的内部排序，所以随机访问查找就没有意义了。因此，要查找 **Collection** 中的元素必须使用迭代器。\n",
    "\n",
    "下面这个示例演示了 **Collection** 的所有方法。这里以 **ArrayList** 为例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/CollectionMethods.java\n",
    "// Things you can do with all Collections\n",
    "import java.util.*;\n",
    "import static onjava.HTMLColors.*;\n",
    "\n",
    "public class CollectionMethods {\n",
    "  public static void main(String[] args) {\n",
    "    Collection<String> c =\n",
    "        new ArrayList<>(LIST.subList(0, 4));\n",
    "    c.add(\"ten\");\n",
    "    c.add(\"eleven\");\n",
    "    show(c);\n",
    "    border();\n",
    "    // Make an array from the List:\n",
    "    Object[] array = c.toArray();\n",
    "    // Make a String array from the List:\n",
    "    String[] str = c.toArray(new String[0]);\n",
    "    // Find max and min elements; this means\n",
    "    // different things depending on the way\n",
    "    // the Comparable interface is implemented:\n",
    "    System.out.println(\n",
    "      \"Collections.max(c) = \" + Collections.max(c));\n",
    "    System.out.println(\n",
    "      \"Collections.min(c) = \" + Collections.min(c));\n",
    "    border();\n",
    "    // Add a Collection to another Collection\n",
    "    Collection<String> c2 =\n",
    "        new ArrayList<>(LIST.subList(10, 14));\n",
    "    c.addAll(c2);\n",
    "    show(c);\n",
    "    border();\n",
    "    c.remove(LIST.get(0));\n",
    "    show(c);\n",
    "    border();\n",
    "    // Remove all components that are\n",
    "    // in the argument collection:\n",
    "    c.removeAll(c2);\n",
    "    show(c);\n",
    "    border();\n",
    "    c.addAll(c2);\n",
    "    show(c);\n",
    "    border();\n",
    "    // Is an element in this Collection?\n",
    "    String val = LIST.get(3);\n",
    "    System.out.println(\n",
    "      \"c.contains(\" + val  + \") = \" + c.contains(val));\n",
    "    // Is a Collection in this Collection?\n",
    "    System.out.println(\n",
    "      \"c.containsAll(c2) = \" + c.containsAll(c2));\n",
    "    Collection<String> c3 =\n",
    "      ((List<String>)c).subList(3, 5);\n",
    "    // Keep all the elements that are in both\n",
    "    // c2 and c3 (an intersection of sets):\n",
    "    c2.retainAll(c3);\n",
    "    show(c2);\n",
    "    // Throw away all the elements\n",
    "    // in c2 that also appear in c3:\n",
    "    c2.removeAll(c3);\n",
    "    System.out.println(\n",
    "      \"c2.isEmpty() = \" +  c2.isEmpty());\n",
    "    border();\n",
    "    // Functional operation:\n",
    "    c = new ArrayList<>(LIST);\n",
    "    c.removeIf(s -> !s.startsWith(\"P\"));\n",
    "    c.removeIf(s -> s.startsWith(\"Pale\"));\n",
    "    // Stream operation:\n",
    "    c.stream().forEach(System.out::println);\n",
    "    c.clear(); // Remove all elements\n",
    "    System.out.println(\"after c.clear():\" + c);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "AliceBlue\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "ten\n",
    "eleven\n",
    "******************************\n",
    "Collections.max(c) = ten\n",
    "Collections.min(c) = AliceBlue\n",
    "******************************\n",
    "AliceBlue\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "ten\n",
    "eleven\n",
    "Brown\n",
    "BurlyWood\n",
    "CadetBlue\n",
    "Chartreuse\n",
    "******************************\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "ten\n",
    "eleven\n",
    "Brown\n",
    "BurlyWood\n",
    "CadetBlue\n",
    "Chartreuse\n",
    "******************************\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "ten\n",
    "eleven\n",
    "******************************\n",
    "AntiqueWhite\n",
    "Aquamarine\n",
    "Azure\n",
    "ten\n",
    "eleven\n",
    "Brown\n",
    "BurlyWood\n",
    "CadetBlue\n",
    "Chartreuse\n",
    "******************************\n",
    "c.contains(Azure) = true\n",
    "c.containsAll(c2) = true\n",
    "c2.isEmpty() = true\n",
    "******************************\n",
    "PapayaWhip\n",
    "PeachPuff\n",
    "Peru\n",
    "Pink\n",
    "Plum\n",
    "PowderBlue\n",
    "Purple\n",
    "after c.clear():[]\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了只演示 **Collection** 接口的方法，而没有其它额外的内容，所以这里创建包含不同数据集的 **ArrayList** ，并向上转型为 **Collection** 对象。\n",
    "\n",
    "<!-- Optional Operations -->\n",
    "## 可选操作\n",
    "\n",
    "在 **Collection** 接口中执行各种添加和删除操作的方法是 *可选操作* （optional operations）。这意味着实现类不需要为这些方法提供功能定义。\n",
    "\n",
    "这是一种非常不寻常的定义接口的方式。正如我们所知，接口是一种合约（contract）。它表达的意思是，“无论你如何选择实现这个接口，我保证你可以将这些消息发送到这个对象”（我在这里使用术语“接口”来描述正式的 **interface** 关键字和“任何类或子类都支持的方法”的更一般含义）。但“可选”操作违反了这一基本原则，它表示调用某些方法不会执行有意义的行为。相反，它们会抛出异常！这看起来似乎丢失了编译时的类型安全性。\n",
    "\n",
    "其实没那么糟糕。如果操作是可选的，编译器仍然能够限制你仅调用该接口中的方法。它不像动态语言那样，可以为任何对象调用任何方法，并在运行时查找特定的调用是否可行。[^2]此外，大多数将 **Collection** 作为参数的方法仅从该 **Collection** 中读取，并且 **Collection** 的所有“读取”方法都不是可选的。\n",
    "\n",
    "为什么要将方法定义为“可选”的？因为这样做可以防止设计中的接口爆炸。集合库的其他设计往往会产生令人困惑的过多接口来描述主题的每个变体。这甚至使得不可能捕获到接口中的所有特殊情况，因为总有人能发明一个新的接口。“不支持的操作（unsupported operation）”这种方式实现了Java集合库的一个重要目标：集合要易于学习和使用。不支持的操作是一种特殊情况，可以推迟到必要的时候。但是，要使用此方法：\n",
    "\n",
    "1. **UnsupportedOperationException** 必须是一个罕见的事件。也就是说，对于大多数类，所有操作都应该起作用，并且只有在特殊情况下才应该不支持某项操作。这在Java集合库中是正确的，因为99%的时间使用到的类 —— **ArrayList** ， **LinkedList** ， **HashSet** 和 **HashMap** ，以及其他具体实现，都支持所有操作。该设计确实为创建一个新的 **Collection** 提供了一个“后门”，可以不为 **Collection** 接口中的所有方法都提供有意义的定义，这些定义仍然适合现有的类库。\n",
    "\n",
    "2. 当不支持某个操作时， **UnsupportedOperationException** 应该出现在实现阶段，而不是在将产品发送给客户之后。毕竟，这个异常表示编程错误：错误地使用了一个具体实现。\n",
    "\n",
    "值得注意的是，不支持的操作只能在运行时检测到，因此这代表动态类型检查。如果你来自像 C++ 这样的静态类型语言，Java 可能看起来只是另一种静态类型语言。当然， Java 肯定有静态类型检查，但它也有大量的动态类型，因此很难说它只是静态语言或动态语言。一旦你开始注意到这一点，你就会开始看到 Java 中动态类型检查的其他示例。\n",
    "\n",
    "<!-- Unsupported Operations -->\n",
    "### 不支持的操作\n",
    "\n",
    "不支持的操作的常见来源是由固定大小的数据结构所支持的集合。使用 `Arrays.asList()` 方法将数组转换为 **List** 时，就会得到这样的集合。此外，还可以选择使用 **Collections** 类中的“不可修改（unmodifiable）”方法使任何集合（包括 **Map** ）抛出 **UnsupportedOperationException** 异常。此示例展示了这两种情况："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/Unsupported.java\n",
    "// Unsupported operations in Java collections\n",
    "import java.util.*;\n",
    "\n",
    "public class Unsupported {\n",
    "  static void\n",
    "  check(String description, Runnable tst) {\n",
    "    try {\n",
    "      tst.run();\n",
    "    } catch(Exception e) {\n",
    "      System.out.println(description + \"(): \" + e);\n",
    "    }\n",
    "  }\n",
    "  static void test(String msg, List<String> list) {\n",
    "    System.out.println(\"--- \" + msg + \" ---\");\n",
    "    Collection<String> c = list;\n",
    "    Collection<String> subList = list.subList(1,8);\n",
    "    // Copy of the sublist:\n",
    "    Collection<String> c2 = new ArrayList<>(subList);\n",
    "    check(\"retainAll\", () -> c.retainAll(c2));\n",
    "    check(\"removeAll\", () -> c.removeAll(c2));\n",
    "    check(\"clear\", () -> c.clear());\n",
    "    check(\"add\", () -> c.add(\"X\"));\n",
    "    check(\"addAll\", () -> c.addAll(c2));\n",
    "    check(\"remove\", () -> c.remove(\"C\"));\n",
    "    // The List.set() method modifies the value but\n",
    "    // doesn't change the size of the data structure:\n",
    "    check(\"List.set\", () -> list.set(0, \"X\"));\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    List<String> list = Arrays.asList(\n",
    "      \"A B C D E F G H I J K L\".split(\" \"));\n",
    "    test(\"Modifiable Copy\", new ArrayList<>(list));\n",
    "    test(\"Arrays.asList()\", list);\n",
    "    test(\"unmodifiableList()\",\n",
    "      Collections.unmodifiableList(\n",
    "        new ArrayList<>(list)));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "--- Modifiable Copy ---\n",
    "--- Arrays.asList() ---\n",
    "retainAll(): java.lang.UnsupportedOperationException\n",
    "removeAll(): java.lang.UnsupportedOperationException\n",
    "clear(): java.lang.UnsupportedOperationException\n",
    "add(): java.lang.UnsupportedOperationException\n",
    "addAll(): java.lang.UnsupportedOperationException\n",
    "remove(): java.lang.UnsupportedOperationException\n",
    "--- unmodifiableList() ---\n",
    "retainAll(): java.lang.UnsupportedOperationException\n",
    "removeAll(): java.lang.UnsupportedOperationException\n",
    "clear(): java.lang.UnsupportedOperationException\n",
    "add(): java.lang.UnsupportedOperationException\n",
    "addAll(): java.lang.UnsupportedOperationException\n",
    "remove(): java.lang.UnsupportedOperationException\n",
    "List.set(): java.lang.UnsupportedOperationException\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因为 `Arrays.asList()` 生成的 **List** 由一个固定大小的数组所支持，所以唯一支持的操作是那些不改变数组大小的操作。任何会导致更改基础数据结构大小的方法都会产生 **UnsupportedOperationException** 异常，来说明这是对不支持的方法的调用（编程错误）。\n",
    "\n",
    "请注意，始终可以将 `Arrays.asList()` 的结果作为一个参数传递给任何 **Collection** 的构造方法（或使用 `addAll()` 方法或静态的 `Collections.addAll()` 方法）来创建一个允许使用所有方法的常规集合，在主方法中第一次调用 `test()` 时显示了这种情况。这种调用产生了一个新的可调整大小的底层数据结构。\n",
    "\n",
    "**Collections** 类中的“unmodifiable”方法会将集合包装一个代理中，如果执行任何想要修改集合的操作，则该代理会生成 **UnsupportedOperationException** 异常。使用这些方法的目的是生成一个“常量”集合对象。稍后将描述“unmodifiable“集合方法的完整列表。\n",
    "\n",
    "`test()` 中的最后一个 `check()` 用于测试**List** 的 `set()` 方法。这里，“不支持的操作”技术的粒度（granularity）就派上用场了，得到的“接口”可以通过一种方法在 `Arrays.asList()` 返回的对象和 `Collections.unmodifiableList()` 返回的对象之间变换。 `Arrays.asList()` 返回固定大小的 **List** ，而 `Collections.unmodifiableList()` 生成无法更改的 **List** 。如输出中所示， `Arrays.asList()` 返回的 **List** 中的元素是可以修改的，因为这不会违反该 **List** 的“固定大小”特性。但很明显， `unmodifiableList()` 的结果不应该以任何方式修改。如果使用接口来描述，则需要两个额外的接口，一个具有可用的 `set()` 方法，而另一个没有。 **Collection** 的各种不可修改的子类型都将需要额外的接口。\n",
    "\n",
    "如果一个方法将一个集合作为它的参数，那么它的文档应该说明必须实现哪些可选方法。\n",
    "\n",
    "<!-- Sets and Storage Order -->\n",
    "## Set和存储顺序\n",
    "\n",
    "[第十二章 集合]()章节中的 **Set** 有关示例对 **Set** 的基本操作做了很好的介绍。 但是，这些示例可以方便地使用预定义的 Java 类型，例如 **Integer** 和 **String** ，它们可以在集合中使用。在创建自己的类型时请注意， **Set** （以及稍后会看到的 **Map** ）需要一种维护存储顺序的方法，该顺序因 **Set** 的不同实现而异。因此，不同的 **Set** 实现不仅具有不同的行为，而且它们对可以放入特定 **Set** 中的对象类型也有不同的要求：\n",
    "\n",
    "| **Set** 类型 | 约束 |\n",
    "| :---: | :--- |\n",
    "| **Set(interface)** | 添加到 **Set** 中的每个元素必须是唯一的，否则，**Set** 不会添加重复元素。添加到 **Set** 的元素必须至少定义 `equals()` 方法以建立对象唯一性。 **Set** 与 **Collection** 具有完全相同的接口。 **Set** 接口不保证它将以任何特定顺序维护其元素。 |\n",
    "| **HashSet\\*** | 注重快速查找元素的集合，其中元素必须定义 `hashCode()` 和 `equals()` 方法。 |\n",
    "| **TreeSet** | 由树支持的有序 **Set**。这样，就可以从 **Set** 中获取有序序列，其中元素必须实现 **Comparable** 接口。 |\n",
    "| **LinkedHashSet** | 具有 **HashSet** 的查找速度，但在内部使用链表维护元素的插入顺序。因此，当在遍历 **Set** 时，结果将按元素的插入顺序显示。元素必须定义 `hashCode()` 和 `equals()` 方法。 |\n",
    "\n",
    "**HashSet** 上的星号表示，在没有其他约束的情况下，这应该是你的默认选择，因为它针对速度进行了优化。\n",
    "\n",
    "定义 `hashCode()` 方法在[附录:理解equals和hashCode方法]()中进行了描述。必须为散列和树存储结构创建 `equals()` 方法，但只有当把类放在 **HashSet** 中时才需要 `hashCode()` （当然这很有可能，因为 **HashSet** 通常应该是作为 **Set** 实现的首选）或 **LinkedHashSet** 。 但是，作为一种良好的编程风格，在覆盖 `equals()` 时应始终覆盖 `hashCode()` 。\n",
    "\n",
    "下面的示例演示了成功使用具有特定 **Set** 实现的类型所需的方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/TypesForSets.java\n",
    "// Methods necessary to put your own type in a Set\n",
    "import java.util.*;\n",
    "import java.util.function.*;\n",
    "import java.util.Objects;\n",
    "\n",
    "class SetType {\n",
    "  protected int i;\n",
    "  SetType(int n) { i = n; }\n",
    "  @Override\n",
    "  public boolean equals(Object o) {\n",
    "    return o instanceof SetType &&\n",
    "      Objects.equals(i, ((SetType)o).i);\n",
    "  }\n",
    "  @Override\n",
    "  public String toString() {\n",
    "    return Integer.toString(i);\n",
    "  }\n",
    "}\n",
    "\n",
    "class HashType extends SetType {\n",
    "  HashType(int n) { super(n); }\n",
    "  @Override\n",
    "  public int hashCode() {\n",
    "    return Objects.hashCode(i);\n",
    "  }\n",
    "}\n",
    "\n",
    "class TreeType extends SetType\n",
    "implements Comparable<TreeType> {\n",
    "  TreeType(int n) { super(n); }\n",
    "  @Override\n",
    "  public int compareTo(TreeType arg) {\n",
    "    return Integer.compare(arg.i, i);\n",
    "    // Equivalent to:\n",
    "    // return arg.i < i ? -1 : (arg.i == i ? 0 : 1);\n",
    "  }\n",
    "}\n",
    "\n",
    "public class TypesForSets {\n",
    "  static <T> void\n",
    "  fill(Set<T> set, Function<Integer, T> type) {\n",
    "    for(int i = 10; i >= 5; i--) // Descending\n",
    "      set.add(type.apply(i));\n",
    "    for(int i = 0; i < 5; i++) // Ascending\n",
    "      set.add(type.apply(i));\n",
    "  }\n",
    "  static <T> void\n",
    "  test(Set<T> set, Function<Integer, T> type) {\n",
    "    fill(set, type);\n",
    "    fill(set, type); // Try to add duplicates\n",
    "    fill(set, type);\n",
    "    System.out.println(set);\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    test(new HashSet<>(), HashType::new);\n",
    "    test(new LinkedHashSet<>(), HashType::new);\n",
    "    test(new TreeSet<>(), TreeType::new);\n",
    "    // Things that don't work:\n",
    "    test(new HashSet<>(), SetType::new);\n",
    "    test(new HashSet<>(), TreeType::new);\n",
    "    test(new LinkedHashSet<>(), SetType::new);\n",
    "    test(new LinkedHashSet<>(), TreeType::new);\n",
    "    try {\n",
    "      test(new TreeSet<>(), SetType::new);\n",
    "    } catch(Exception e) {\n",
    "      System.out.println(e.getMessage());\n",
    "    }\n",
    "    try {\n",
    "      test(new TreeSet<>(), HashType::new);\n",
    "    } catch(Exception e) {\n",
    "      System.out.println(e.getMessage());\n",
    "    }\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n",
    "[10, 9, 8, 7, 6, 5, 0, 1, 2, 3, 4]\n",
    "[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n",
    "[1, 6, 8, 6, 2, 7, 8, 9, 4, 10, 7, 5, 1, 3, 4, 9, 9,\n",
    "10, 5, 3, 2, 0, 4, 1, 2, 0, 8, 3, 0, 10, 6, 5, 7]\n",
    "[3, 1, 4, 8, 7, 6, 9, 5, 3, 0, 10, 5, 5, 10, 7, 8, 8,\n",
    "9, 1, 4, 10, 2, 6, 9, 1, 6, 0, 3, 2, 0, 7, 2, 4]\n",
    "[10, 9, 8, 7, 6, 5, 0, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5,\n",
    "0, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5, 0, 1, 2, 3, 4]\n",
    "[10, 9, 8, 7, 6, 5, 0, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5,\n",
    "0, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5, 0, 1, 2, 3, 4]\n",
    "SetType cannot be cast to java.lang.Comparable\n",
    "HashType cannot be cast to java.lang.Comparable\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了证明特定 **Set** 需要哪些方法，同时避免代码重复，这里创建了三个类。基类 **SetType** 存储一个 **int** 值，并通过 `toString()` 方法打印它。由于存储在 **Set** 中的所有类都必须具有 `equals()` ，因此该方法也放在基类中。基于 `int i` 来判断元素是否相等。\n",
    "\n",
    "**HashType** 继承自 **SetType** ，并添加了 `hashCode()` 方法，该方法对于 **Set** 的散列实现是必需的。\n",
    "\n",
    "要在任何类型的有序集合中使用对象，由 **TreeType** 实现的 **Comparable** 接口都是必需的，例如 **SortedSet** （ **TreeSet** 是其唯一实现）。在 `compareTo()` 中，请注意我没有使用“简单明了”的形式： `return i-i2` 。虽然这是一个常见的编程错误，但只有当 **i** 和 **i2** 是“无符号（unsigned）”整型时才能正常工作（如果 Java 有一个“unsigned”关键字的话，不过它没有）。它破坏了 Java 的有符号 **int** ，它不足以代表两个有符号整数的差异。如果 **i** 是一个大的正整数而 **j** 是一个大的负整数， `i-j` 将溢出并返回一个负值，这不是我们所需要的。\n",
    "\n",
    "通常希望 `compareTo()` 方法生成与 `equals()` 方法一致的自然顺序。如果 `equals()` 对于特定比较产生 **true**，则 `compareTo()` 应该为该比较返回结果 零，并且如果 `equals()` 为比较产生 **false** ，则 `compareTo()` 应该为该比较产生非零结果。\n",
    "\n",
    "在 **TypesForSets** 中， `fill()` 和 `test()` 都是使用泛型定义的，以防止代码重复。为了验证 **Set** 的行为， `test()` 在测试集上调用 `fill()` 三次，尝试引入重复的对象。 `fill()` 方法的参数可以接收任意一个 **Set** 类型，以及生成该类型的 **Function** 对象。因为此示例中使用的所有对象都有一个带有单个 **int** 参数的构造方法，所以可以将构造方法作为此 **Function** 传递，它将提供用于填充 **Set** 的对象。\n",
    "\n",
    "请注意， `fill()` 方法按降序添加前五个元素，按升序添加后五个元素，以此来指出生成的存储顺序。输出显示 **HashSet** 按升序保留元素，但是，在[附录:理解equals和hashCode方法]()中，你会发现这只是偶然的，因为散列会创建自己的存储顺序。这里只是因为元素是一个简单的 **int** ，在这种情况下它是升序的。 **LinkedHashSet** 按照插入顺序保存元素，**TreeSet** 按排序顺序维护元素（在此示例中因为 `compareTo()` 的实现方式，所以元素按降序排列。）\n",
    "\n",
    "特定的 **Set** 类型一般都有所必需的操作，如果尝试使用没能正确支持这些操作的类型，那么事情就会出错。将没有重新定义 `hashCode()` 方法的 **SetType** 或 **TreeType** 对象放入任何散列实现会导致重复值，因此违反了 **Set** 的主要契约。 这是相当令人不安的，因为这甚至不产生运行时错误。但是，默认的 `hashCode()` 是合法的，所以即使它是不正确的，这也是合法的行为。确保此类程序正确性的唯一可靠方法是将单元测试合并到构建系统中。\n",
    "\n",
    "如果尝试在 **TreeSet** 中使用没有实现 **Comparable** 接口的类型，则会得到更明确的结果：当 **TreeSet** 尝试将对象用作一个 **Comparable** 时，将会抛出异常。\n",
    "\n",
    "<!-- SortedSet -->\n",
    "### SortedSet\n",
    "\n",
    "**SortedSet** 中的元素保证按排序规则顺序， **SortedSet** 接口中的以下方法可以产生其他功能：\n",
    "\n",
    "- `Comparator comparator()` ：生成用于此 **Set** 的**Comparator** 或 **null** 来用于自然排序。\n",
    "- `Object first()` ：返回第一个元素。\n",
    "- `Object last()` ：返回最后一个元素。\n",
    "- `SortedSet subSet(fromElement，toElement)` ：使用 **fromElement** （包含）和 **toElement** （不包括）中的元素生成此 **Set** 的一个视图。\n",
    "- `SortedSet headSet(toElement)` ：使用顺序在 **toElement** 之前的元素生成此 **Set** 的一个视图。\n",
    "- `SortedSet tailSet(fromElement)` ：使用顺序在 **fromElement** 之后（包含 **fromElement** ）的元素生成此 **Set** 的一个视图。\n",
    "\n",
    "下面是一个简单的演示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/SortedSetDemo.java\n",
    "import java.util.*;\n",
    "import static java.util.stream.Collectors.*;\n",
    "\n",
    "public class SortedSetDemo {\n",
    "  public static void main(String[] args) {\n",
    "    SortedSet<String> sortedSet =\n",
    "      Arrays.stream(\n",
    "        \"one two three four five six seven eight\"\n",
    "        .split(\" \"))\n",
    "        .collect(toCollection(TreeSet::new));\n",
    "    System.out.println(sortedSet);\n",
    "    String low = sortedSet.first();\n",
    "    String high = sortedSet.last();\n",
    "    System.out.println(low);\n",
    "    System.out.println(high);\n",
    "    Iterator<String> it = sortedSet.iterator();\n",
    "    for(int i = 0; i <= 6; i++) {\n",
    "      if(i == 3) low = it.next();\n",
    "      if(i == 6) high = it.next();\n",
    "      else it.next();\n",
    "    }\n",
    "    System.out.println(low);\n",
    "    System.out.println(high);\n",
    "    System.out.println(sortedSet.subSet(low, high));\n",
    "    System.out.println(sortedSet.headSet(high));\n",
    "    System.out.println(sortedSet.tailSet(low));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[eight, five, four, one, seven, six, three, two]\n",
    "eight\n",
    "two\n",
    "one\n",
    "two\n",
    "[one, seven, six, three]\n",
    "[eight, five, four, one, seven, six, three]\n",
    "[one, seven, six, three, two]\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意， **SortedSet** 表示“根据对象的比较函数进行排序”，而不是“根据插入顺序”。可以使用 **LinkedHashSet** 保留元素的插入顺序。\n",
    "\n",
    "<!-- Queues -->\n",
    "## 队列\n",
    "\n",
    "有许多 **Queue** 实现，其中大多数是为并发应用程序设计的。许多实现都是通过排序行为而不是性能来区分的。这是一个涉及大多数 **Queue** 实现的基本示例，包括基于并发的队列。队列将元素从一端放入并从另一端取出："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/QueueBehavior.java\n",
    "// Compares basic behavior\n",
    "import java.util.*;\n",
    "import java.util.stream.*;\n",
    "import java.util.concurrent.*;\n",
    "\n",
    "public class QueueBehavior {\n",
    "  static Stream<String> strings() {\n",
    "    return Arrays.stream(\n",
    "      (\"one two three four five six seven \" +\n",
    "       \"eight nine ten\").split(\" \"));\n",
    "  }\n",
    "  static void test(int id, Queue<String> queue) {\n",
    "    System.out.print(id + \": \");\n",
    "    strings().map(queue::offer).count();\n",
    "    while(queue.peek() != null)\n",
    "      System.out.print(queue.remove() + \" \");\n",
    "    System.out.println();\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    int count = 10;\n",
    "    test(1, new LinkedList<>());\n",
    "    test(2, new PriorityQueue<>());\n",
    "    test(3, new ArrayBlockingQueue<>(count));\n",
    "    test(4, new ConcurrentLinkedQueue<>());\n",
    "    test(5, new LinkedBlockingQueue<>());\n",
    "    test(6, new PriorityBlockingQueue<>());\n",
    "    test(7, new ArrayDeque<>());\n",
    "    test(8, new ConcurrentLinkedDeque<>());\n",
    "    test(9, new LinkedBlockingDeque<>());\n",
    "    test(10, new LinkedTransferQueue<>());\n",
    "    test(11, new SynchronousQueue<>());\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "1: one two three four five six seven eight nine ten\n",
    "2: eight five four nine one seven six ten three two\n",
    "3: one two three four five six seven eight nine ten\n",
    "4: one two three four five six seven eight nine ten\n",
    "5: one two three four five six seven eight nine ten\n",
    "6: eight five four nine one seven six ten three two\n",
    "7: one two three four five six seven eight nine ten\n",
    "8: one two three four five six seven eight nine ten\n",
    "9: one two three four five six seven eight nine ten\n",
    "10: one two three four five six seven eight nine ten\n",
    "11:\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deque** 接口也继承自 **Queue** 。 除优先级队列外，**Queue** 按照元素的插入顺序生成元素。 在此示例中，**SynchronousQueue** 不会产生任何结果，因为它是一个阻塞队列，其中每个插入操作必须等待另一个线程执行相应的删除操作，反之亦然。\n",
    "\n",
    "<!-- Priority Queues -->\n",
    "### 优先级队列\n",
    "\n",
    "考虑一个待办事项列表，其中每个对象包含一个 **String** 以及主要和次要优先级值。通过实现 **Comparable** 接口来控制此待办事项列表的顺序："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/ToDoList.java\n",
    "// A more complex use of PriorityQueue\n",
    "import java.util.*;\n",
    "\n",
    "class ToDoItem implements Comparable<ToDoItem> {\n",
    "  private char primary;\n",
    "  private int secondary;\n",
    "  private String item;\n",
    "  ToDoItem(String td, char pri, int sec) {\n",
    "    primary = pri;\n",
    "    secondary = sec;\n",
    "    item = td;\n",
    "  }\n",
    "  @Override\n",
    "  public int compareTo(ToDoItem arg) {\n",
    "    if(primary > arg.primary)\n",
    "      return +1;\n",
    "    if(primary == arg.primary)\n",
    "      if(secondary > arg.secondary)\n",
    "        return +1;\n",
    "      else if(secondary == arg.secondary)\n",
    "        return 0;\n",
    "    return -1;\n",
    "  }\n",
    "  @Override\n",
    "  public String toString() {\n",
    "    return Character.toString(primary) +\n",
    "      secondary + \": \" + item;\n",
    "  }\n",
    "}\n",
    "\n",
    "class ToDoList {\n",
    "  public static void main(String[] args) {\n",
    "    PriorityQueue<ToDoItem> toDo =\n",
    "      new PriorityQueue<>();\n",
    "    toDo.add(new ToDoItem(\"Empty trash\", 'C', 4));\n",
    "    toDo.add(new ToDoItem(\"Feed dog\", 'A', 2));\n",
    "    toDo.add(new ToDoItem(\"Feed bird\", 'B', 7));\n",
    "    toDo.add(new ToDoItem(\"Mow lawn\", 'C', 3));\n",
    "    toDo.add(new ToDoItem(\"Water lawn\", 'A', 1));\n",
    "    toDo.add(new ToDoItem(\"Feed cat\", 'B', 1));\n",
    "    while(!toDo.isEmpty())\n",
    "      System.out.println(toDo.remove());\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "A1: Water lawn\n",
    "A2: Feed dog\n",
    "B1: Feed cat\n",
    "B7: Feed bird\n",
    "C3: Mow lawn\n",
    "C4: Empty trash\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这展示了通过优先级队列自动排序待办事项。\n",
    "\n",
    "<!-- Deque -->\n",
    "### 双端队列\n",
    "\n",
    "**Deque** （双端队列）就像一个队列，但是可以从任一端添加和删除元素。 Java 6为 **Deque** 添加了一个显式接口。以下是对实现了 **Deque** 的类的最基本的 **Deque** 方法的测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/SimpleDeques.java\n",
    "// Very basic test of Deques\n",
    "import java.util.*;\n",
    "import java.util.concurrent.*;\n",
    "import java.util.function.*;\n",
    "\n",
    "class CountString implements Supplier<String> {\n",
    "  private int n = 0;\n",
    "  CountString() {}\n",
    "  CountString(int start) { n = start; }\n",
    "  @Override\n",
    "  public String get() {\n",
    "    return Integer.toString(n++);\n",
    "  }\n",
    "}\n",
    "\n",
    "public class SimpleDeques {\n",
    "  static void test(Deque<String> deque) {\n",
    "    CountString s1 = new CountString(),\n",
    "                s2 = new CountString(20);\n",
    "    for(int n = 0; n < 8; n++) {\n",
    "        deque.offerFirst(s1.get());\n",
    "        deque.offerLast(s2.get()); // Same as offer()\n",
    "    }\n",
    "    System.out.println(deque);\n",
    "    String result = \"\";\n",
    "    while(deque.size() > 0) {\n",
    "      System.out.print(deque.peekFirst() + \" \");\n",
    "      result += deque.pollFirst() + \" \";\n",
    "      System.out.print(deque.peekLast() + \" \");\n",
    "      result += deque.pollLast() + \" \";\n",
    "    }\n",
    "    System.out.println(\"\\n\" + result);\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    int count = 10;\n",
    "    System.out.println(\"LinkedList\");\n",
    "    test(new LinkedList<>());\n",
    "    System.out.println(\"ArrayDeque\");\n",
    "    test(new ArrayDeque<>());\n",
    "    System.out.println(\"LinkedBlockingDeque\");\n",
    "    test(new LinkedBlockingDeque<>(count));\n",
    "    System.out.println(\"ConcurrentLinkedDeque\");\n",
    "    test(new ConcurrentLinkedDeque<>());\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "LinkedList\n",
    "[7, 6, 5, 4, 3, 2, 1, 0, 20, 21, 22, 23, 24, 25, 26,\n",
    "27]\n",
    "7 27 6 26 5 25 4 24 3 23 2 22 1 21 0 20\n",
    "7 27 6 26 5 25 4 24 3 23 2 22 1 21 0 20\n",
    "ArrayDeque\n",
    "[7, 6, 5, 4, 3, 2, 1, 0, 20, 21, 22, 23, 24, 25, 26,\n",
    "27]\n",
    "7 27 6 26 5 25 4 24 3 23 2 22 1 21 0 20\n",
    "7 27 6 26 5 25 4 24 3 23 2 22 1 21 0 20\n",
    "LinkedBlockingDeque\n",
    "[4, 3, 2, 1, 0, 20, 21, 22, 23, 24]\n",
    "4 24 3 23 2 22 1 21 0 20\n",
    "4 24 3 23 2 22 1 21 0 20\n",
    "ConcurrentLinkedDeque\n",
    "[7, 6, 5, 4, 3, 2, 1, 0, 20, 21, 22, 23, 24, 25, 26,\n",
    "27]\n",
    "7 27 6 26 5 25 4 24 3 23 2 22 1 21 0 20\n",
    "7 27 6 26 5 25 4 24 3 23 2 22 1 21 0 20\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我只使用了 **Deque** 方法的“offer”和“poll”版本，因为当 **LinkedBlockingDeque** 的大小有限时，这些方法不会抛出异常。请注意， **LinkedBlockingDeque** 仅填充到它的限制大小为止，然后忽略额外的添加。\n",
    "\n",
    "<!-- Understanding Maps -->\n",
    "## 理解Map\n",
    "\n",
    "正如在[第十二章 集合]()章节中所了解到的，**Map**（也称为 *关联数组* ）维护键值关联（对），因此可以使用键来查找值。标准 Java 库包含不同的 **Map** 基本实现，例如 **HashMap** ， **TreeMap** ， **LinkedHashMap** ， **WeakHashMap** ， **ConcurrentHashMap** 和 **IdentityHashMap** 。 它们都具有相同的基本 **Map** 接口，但它们的行为不同，包括效率，键值对的保存顺序和呈现顺序，保存对象的时间，如何在多线程程序中工作，以及如何确定键的相等性。 **Map** 接口的实现数量应该告诉你一些关于此工具重要性的信息。\n",
    "\n",
    "为了更深入地了解 **Map** ，学习如何构造关联数组会很有帮助。下面是一个非常简单的实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/AssociativeArray.java\n",
    "// Associates keys with values\n",
    "\n",
    "public class AssociativeArray<K, V> {\n",
    "  private Object[][] pairs;\n",
    "  private int index;\n",
    "  public AssociativeArray(int length) {\n",
    "    pairs = new Object[length][2];\n",
    "  }\n",
    "  public void put(K key, V value) {\n",
    "    if(index >= pairs.length)\n",
    "      throw new ArrayIndexOutOfBoundsException();\n",
    "    pairs[index++] = new Object[]{ key, value };\n",
    "  }\n",
    "  @SuppressWarnings(\"unchecked\")\n",
    "  public V get(K key) {\n",
    "    for(int i = 0; i < index; i++)\n",
    "      if(key.equals(pairs[i][0]))\n",
    "        return (V)pairs[i][1];\n",
    "    return null; // Did not find key\n",
    "  }\n",
    "  @Override\n",
    "  public String toString() {\n",
    "    StringBuilder result = new StringBuilder();\n",
    "    for(int i = 0; i < index; i++) {\n",
    "      result.append(pairs[i][0].toString());\n",
    "      result.append(\" : \");\n",
    "      result.append(pairs[i][1].toString());\n",
    "      if(i < index - 1)\n",
    "        result.append(\"\\n\");\n",
    "    }\n",
    "    return result.toString();\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    AssociativeArray<String,String> map =\n",
    "      new AssociativeArray<>(6);\n",
    "    map.put(\"sky\", \"blue\");\n",
    "    map.put(\"grass\", \"green\");\n",
    "    map.put(\"ocean\", \"dancing\");\n",
    "    map.put(\"tree\", \"tall\");\n",
    "    map.put(\"earth\", \"brown\");\n",
    "    map.put(\"sun\", \"warm\");\n",
    "    try {\n",
    "      map.put(\"extra\", \"object\"); // Past the end\n",
    "    } catch(ArrayIndexOutOfBoundsException e) {\n",
    "      System.out.println(\"Too many objects!\");\n",
    "    }\n",
    "    System.out.println(map);\n",
    "    System.out.println(map.get(\"ocean\"));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "Too many objects!\n",
    "sky : blue\n",
    "grass : green\n",
    "ocean : dancing\n",
    "tree : tall\n",
    "earth : brown\n",
    "sun : warm\n",
    "dancing\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关联数组中的基本方法是 `put()` 和 `get()` ，但为了便于显示，重写了 `toString()` 方法以打印键值对。为了显示它的工作原理，主方法加载一个带有字符串对的 **AssociativeArray** 并打印生成的映射，然后调用其中一个值的 `get()` 方法。\n",
    "\n",
    "要使用 `get()` 方法，可以传入要查找的 **key** ，它将生成相关联的值作为结果，如果找不到则返回 **null** 。 `get()` 方法使用可能是效率最低的方法来定位值：从数组的头部开始并使用 `equals()` 来比较键。但这里是侧重于简单，而不是效率。\n",
    "\n",
    "这个版本很有启发性，但它不是很有效，而且它只有一个固定的大小，这是不灵活的。幸运的是， **java.util** 中的那些 **Map** 没有这些问题。\n",
    "\n",
    "<!-- Performance -->\n",
    "### 性能\n",
    "\n",
    "性能是 **Map** 的基本问题，在 `get()` 中使用线性方法搜索一个键时会非常慢。这就是 **HashMap** 要加速的地方。它使用一个称为 *哈希码* 的特殊值来替代慢速搜索一个键。哈希码是一种从相关对象中获取一些信息并将其转换为该对象的“相对唯一” **int** 的方法。 `hashCode()` 是根类 **Object** 中的一个方法，因此所有 Java 对象都可以生成哈希码。 **HashMap** 获取对象的 `hashCode()` 并使用它来快速搜索键。这就使得性能有了显著的提升。[^3]\n",
    "\n",
    "以下是基本的 **Map** 实现。 **HashMap**上的星号表示，在没有其他约束的情况下，这应该是你的默认选择，因为它针对速度进行了优化。其他实现强调其他特性，因此不如 **HashMap** 快。\n",
    "\n",
    "| **Map** 实现 | 描述 |\n",
    "| :---: | :--- |\n",
    "| **HashMap\\*** | 基于哈希表的实现。（使用此类来代替 **Hashtable** 。）为插入和定位键值对提供了常数时间性能。可以通过构造方法调整性能，这些构造方法允许你设置哈希表的容量和装填因子。 |\n",
    "| **LinkedHashMap** | 与 **HashMap** 类似，但是当遍历时，可以按插入顺序或最近最少使用（LRU）顺序获取键值对。只比 **HashMap** 略慢，一个例外是在迭代时，由于其使用链表维护内部顺序，所以会更快些。 |\n",
    "| **TreeMap** | 基于红黑树的实现。当查看键或键值对时，它们按排序顺序（由 **Comparable** 或 **Comparator** 确定）。 **TreeMap** 的侧重点是按排序顺序获得结果。 **TreeMap** 是唯一使用 `subMap()` 方法的 **Map** ，它返回红黑树的一部分。 |\n",
    "| **WeakHashMap** | 一种具有 *弱键*（weak keys） 的 **Map** ，为了解决某些类型的问题，它允许释放 **Map** 所引用的对象。如果在 **Map** 外没有对特定键的引用，则可以对该键进行垃圾回收。 |\n",
    "| **ConcurrentHashMap** | 不使用同步锁定的线程安全 **Mao** 。这在[第二十四章 并发编程]() 一章中讨论。 |\n",
    "| **IdentityHashMap** | 使用 `==` 而不是 `equals()` 来比较键。仅用于解决特殊问题，不适用于一般用途。 |\n",
    "\n",
    "散列是在 **Map** 中存储元素的最常用方法。\n",
    "\n",
    "**Map** 中使用的键的要求与 **Set** 中的元素的要求相同。可以在 **TypesForSets.java** 中看到这些。任何键必须具有 `equals()` 方法。如果键用于散列映射，则它还必须具有正确的 `hashCode()` 方法。如果键在 **TreeMap** 中使用，则必须实现 **Comparable** 接口。\n",
    "\n",
    "以下示例使用先前定义的 **CountMap** 测试数据集显示通过 **Map** 接口可用的操作："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/MapOps.java\n",
    "// Things you can do with Maps\n",
    "import java.util.concurrent.*;\n",
    "import java.util.*;\n",
    "import onjava.*;\n",
    "\n",
    "public class MapOps {\n",
    "  public static\n",
    "  void printKeys(Map<Integer,String> map) {\n",
    "    System.out.print(\"Size = \" + map.size() + \", \");\n",
    "    System.out.print(\"Keys: \");\n",
    "    // Produce a Set of the keys:\n",
    "    System.out.println(map.keySet());\n",
    "  }\n",
    "  public static\n",
    "  void test(Map<Integer,String> map) {\n",
    "    System.out.println(\n",
    "      map.getClass().getSimpleName());\n",
    "    map.putAll(new CountMap(25));\n",
    "    // Map has 'Set' behavior for keys:\n",
    "    map.putAll(new CountMap(25));\n",
    "    printKeys(map);\n",
    "    // Producing a Collection of the values:\n",
    "    System.out.print(\"Values: \");\n",
    "    System.out.println(map.values());\n",
    "    System.out.println(map);\n",
    "    System.out.println(\"map.containsKey(11): \" +\n",
    "      map.containsKey(11));\n",
    "    System.out.println(\n",
    "      \"map.get(11): \" + map.get(11));\n",
    "    System.out.println(\"map.containsValue(\\\"F0\\\"): \"\n",
    "      + map.containsValue(\"F0\"));\n",
    "    Integer key = map.keySet().iterator().next();\n",
    "    System.out.println(\"First key in map: \" + key);\n",
    "    map.remove(key);\n",
    "    printKeys(map);\n",
    "    map.clear();\n",
    "    System.out.println(\n",
    "      \"map.isEmpty(): \" + map.isEmpty());\n",
    "    map.putAll(new CountMap(25));\n",
    "    // Operations on the Set change the Map:\n",
    "    map.keySet().removeAll(map.keySet());\n",
    "    System.out.println(\n",
    "      \"map.isEmpty(): \" + map.isEmpty());\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    test(new HashMap<>());\n",
    "    test(new TreeMap<>());\n",
    "    test(new LinkedHashMap<>());\n",
    "    test(new IdentityHashMap<>());\n",
    "    test(new ConcurrentHashMap<>());\n",
    "    test(new WeakHashMap<>());\n",
    "  }\n",
    "}\n",
    "/* Output: (First 11 Lines)\n",
    "HashMap\n",
    "Size = 25, Keys: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,\n",
    "12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]\n",
    "Values: [A0, B0, C0, D0, E0, F0, G0, H0, I0, J0, K0,\n",
    "L0, M0, N0, O0, P0, Q0, R0, S0, T0, U0, V0, W0, X0, Y0]\n",
    "{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0,\n",
    "9=J0, 10=K0, 11=L0, 12=M0, 13=N0, 14=O0, 15=P0, 16=Q0,\n",
    "17=R0, 18=S0, 19=T0, 20=U0, 21=V0, 22=W0, 23=X0, 24=Y0}\n",
    "map.containsKey(11): true\n",
    "map.get(11): L0\n",
    "map.containsValue(\"F0\"): true\n",
    "First key in map: 0\n",
    "Size = 24, Keys: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,\n",
    "12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]\n",
    "map.isEmpty(): true\n",
    "map.isEmpty(): true\n",
    "                  ...\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`printKeys()` 方法演示了如何生成 **Map** 的 **Collection** 视图。 `keySet()` 方法生成一个由 **Map** 中的键组成的 **Set** 。 打印 `values()` 方法的结果会生成一个包含 **Map** 中所有值的 **Collection** 。（请注意，键必须是唯一的，但值可以包含重复项。）由于这些 **Collection** 由 **Map** 支持，因此 **Collection** 中的任何更改都会反映在所关联的 **Map** 中。\n",
    "\n",
    "程序的其余部分提供了每个 **Map** 操作的简单示例，并测试了每种基本类型的 **Map** 。\n",
    "\n",
    "<!-- SortedMap -->\n",
    "### SortedMap\n",
    "\n",
    "使用 **SortedMap** （由 **TreeMap** 或 **ConcurrentSkipListMap** 实现），键保证按排序顺序，这允许在 **SortedMap** 接口中使用这些方法来提供其他功能：\n",
    "\n",
    "- `Comparator comparator()` ：生成用于此 **Map** 的比较器， **null** 表示自然排序。\n",
    "- `T firstKey()` ：返回第一个键。\n",
    "- `T lastKey()` ：返回最后一个键。\n",
    "- `SortedMap subMap(fromKey，toKey)` ：生成此 **Map** 的视图，其中键从 **fromKey**（包括），到 **toKey** （不包括）。\n",
    "- `SortedMap headMap(toKey)` ：使用小于 **toKey** 的键生成此 **Map** 的视图。\n",
    "- `SortedMap tailMap(fromKey)` ：使用大于或等于 **fromKey** 的键生成此 **Map** 的视图。\n",
    "\n",
    "这是一个类似于 **SortedSetDemo.java** 的示例，显示了 **TreeMap** 的这种额外行为："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/SortedMapDemo.java\n",
    "// What you can do with a TreeMap\n",
    "import java.util.*;\n",
    "import onjava.*;\n",
    "\n",
    "public class SortedMapDemo {\n",
    "  public static void main(String[] args) {\n",
    "    TreeMap<Integer,String> sortedMap =\n",
    "      new TreeMap<>(new CountMap(10));\n",
    "    System.out.println(sortedMap);\n",
    "    Integer low = sortedMap.firstKey();\n",
    "    Integer high = sortedMap.lastKey();\n",
    "    System.out.println(low);\n",
    "    System.out.println(high);\n",
    "    Iterator<Integer> it =\n",
    "      sortedMap.keySet().iterator();\n",
    "    for(int i = 0; i <= 6; i++) {\n",
    "      if(i == 3) low = it.next();\n",
    "      if(i == 6) high = it.next();\n",
    "      else it.next();\n",
    "    }\n",
    "    System.out.println(low);\n",
    "    System.out.println(high);\n",
    "    System.out.println(sortedMap.subMap(low, high));\n",
    "    System.out.println(sortedMap.headMap(high));\n",
    "    System.out.println(sortedMap.tailMap(low));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0,\n",
    "9=J0}\n",
    "0\n",
    "9\n",
    "3\n",
    "7\n",
    "{3=D0, 4=E0, 5=F0, 6=G0}\n",
    "{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0}\n",
    "{3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0, 9=J0}\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里，键值对按照键的排序顺序进行排序。因为 **TreeMap** 中存在顺序感，所以“位置”的概念很有意义，因此可以拥有第一个、最后一个元素或子图。\n",
    "\n",
    "<!-- LinkedHashMap -->\n",
    "### LinkedHashMap\n",
    "\n",
    "**LinkedHashMap** 针对速度进行哈希处理，但在遍历期间也会按插入顺序生成键值对（ `System.out.println()` 可以遍历它，因此可以看到遍历的结果）。 此外，可以在构造方法中配置 **LinkedHashMap** 以使用基于访问的 *最近最少使用*（LRU） 算法，因此未访问的元素（因此是删除的候选者）会出现在列表的前面。 这样可以轻松创建一个能够定期清理以节省空间的程序。下面是一个显示这两个功能的简单示例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/LinkedHashMapDemo.java\n",
    "// What you can do with a LinkedHashMap\n",
    "import java.util.*;\n",
    "import onjava.*;\n",
    "\n",
    "public class LinkedHashMapDemo {\n",
    "  public static void main(String[] args) {\n",
    "    LinkedHashMap<Integer,String> linkedMap =\n",
    "      new LinkedHashMap<>(new CountMap(9));\n",
    "    System.out.println(linkedMap);\n",
    "    // Least-recently-used order:\n",
    "    linkedMap =\n",
    "      new LinkedHashMap<>(16, 0.75f, true);\n",
    "    linkedMap.putAll(new CountMap(9));\n",
    "    System.out.println(linkedMap);\n",
    "    for(int i = 0; i < 6; i++)\n",
    "      linkedMap.get(i);\n",
    "    System.out.println(linkedMap);\n",
    "    linkedMap.get(0);\n",
    "    System.out.println(linkedMap);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}\n",
    "{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}\n",
    "{6=G0, 7=H0, 8=I0, 0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0}\n",
    "{6=G0, 7=H0, 8=I0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 0=A0}\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这些键值对确实是按照插入顺序进行遍历，即使对于LRU版本也是如此。 但是，在LRU版本中访问前六项（仅限）后，最后三项将移至列表的前面。然后，当再次访问“ **0** ”后，它移动到了列表的后面。\n",
    "\n",
    "<!-- Utilities -->\n",
    "## 集合工具类\n",
    "\n",
    "集合有许多独立的实用工具程序，在 **java.util.Collections** 中表示为静态方法。之前已经见过其中一些，例如 `addAll()` ， `reverseOrder()` 和 `binarySearch()` 。以下是其他内容（同步和不可修改的实用工具程序将在后面的章节中介绍）。在此表中，在需要的时候使用了泛型：\n",
    "\n",
    "| 方法 | 描述 |\n",
    "| :--- | :--- |\n",
    "| **checkedCollection(Collection\\<T> c, Class\\<T> type)** <br><br> **checkedList(List\\<T> list, Class\\<T> type)** <br><br> **checkedMap(Map\\<K, V> m, Class\\<K> keyType, Class\\<V> valueType)** <br><br> **checkedSet(Set\\<T> s, Class\\<T> type)** <br><br> **checkedSortedMap(SortedMap\\<K, V> m, Class\\<K> keyType, Class\\<V> valueType)** <br><br> **checkedSortedSet(SortedSet\\<T> s, Class\\<T> type)** | 生成 **Collection** 的动态类型安全视图或 **Collection** 的特定子类型。 当无法使用静态检查版本时使用这个版本。 <br><br> 这些方法的使用在[第九章 多态]()章节的“动态类型安全”标题下进行了展示。 |\n",
    "| **max(Collection)** <br><br> **min(Collection)** | 使用 **Collection** 中对象的自然比较方法生成参数集合中的最大或最小元素。 |\n",
    "| **max(Collection, Comparator)** <br><br> **min(Collection, Comparator)** | 使用 **Comparator** 指定的比较方法生成参数集合中的最大或最小元素。 |\n",
    "| **indexOfSubList(List source, List target)** | 返回 **target** 在 **source** 内第一次出现的起始索引，如果不存在则返回 -1。 |\n",
    "| **lastIndexOfSubList(List source, List target)** | 返回 **target** 在 **source** 内最后一次出现的起始索引，如果不存在则返回 -1。 |\n",
    "| **replaceAll(List\\<T> list, T oldVal, T newVal)** | 用 **newVal** 替换列表中所有的 **oldVal** 。 |\n",
    "| **reverse(List)**| 反转列表 |\n",
    "| **reverseOrder()** <br><br> **reverseOrder(Comparator\\<T>)** | 返回一个 **Comparator** ，它与集合中实现了 **comparable\\<T>** 接口的对象的自然顺序相反。第二个版本颠倒了所提供的 **Comparator** 的顺序。 |\n",
    "| **rotate(List, int distance)** | 将所有元素向前移动 **distance** ，将尾部的元素移到开头。（译者注：即循环移动） |\n",
    "| **shuffle(List)** <br><br> **shuffle(List, Random)**  | 随机置换指定列表（即打乱顺序）。第一个版本使用了默认的随机化源，或者也可以使用第二个版本，提供自己的随机化源。 |\n",
    "| **sort(List\\<T>)** <br><br> **sort(List\\<T>, Comparator\\<? super T> c)** | 第一个版本使用元素的自然顺序排序该 **List\\<T>** 。第二个版本根据提供的 **Comparator** 排序。 |\n",
    "| **copy(List\\<? super T> dest, List\\<? extends T> src)** | 将 **src** 中的元素复制到 **dest** 。 |\n",
    "| **swap(List, int i, int j)** | 交换 **List** 中位置 **i** 和 位置 **j** 的元素。可能比你手工编写的速度快。 |\n",
    "| **fill(List\\<? super T>, T x)** | 用 **x** 替换 **List** 中的所有元素。|\n",
    "| **nCopies(int n, T x)** | 返回大小为 **n** 的不可变 **List\\<T>** ，其引用都指向 **x** 。 |\n",
    "| **disjoint(Collection, Collection)** | 如果两个集合没有共同元素，则返回 **true** 。 |\n",
    "| **frequency(Collection, Object x)** | 返回 **Collection** 中，等于 **x** 的元素个数。 |\n",
    "| **emptyList()** <br><br> **emptyMap()** <br><br> **emptySet()** | 返回不可变的空 **List** ， **Map** 或 **Set** 。这些是泛型的，因此生成的 **Collection** 可以被参数化为所需的类型。 |\n",
    "| **singleton(T x)** <br><br> **singletonList(T x)** <br><br> **singletonMap(K key, V value)** | 生成一个不可变的 **List** ， **Set** 或 **Map** ，其中只包含基于给定参数的单个元素。 |\n",
    "| **list(Enumeration\\<T> e)** | 生成一个 **ArrayList\\<T>** ，其中元素为（旧式） **Enumeration** （ **Iterator** 的前身）中的元素。用于从遗留代码向新式转换。 |\n",
    "| **enumeration(Collection\\<T>)** | 为参数集合生成一个旧式的 **Enumeration\\<T>** 。 |\n",
    "\n",
    "请注意， `min（)` 和 `max()` 使用 **Collection** 对象，而不使用 **List** ，因此不必担心是否应对 **Collection** 进行排序。（如前所述，在执行 `binarySearch()` 之前，将会对 **List** 或数组进行`sort()` 排序。）\n",
    "\n",
    "下面是一个示例，展示了上表中大多数实用工具程序的基本用法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/Utilities.java\n",
    "// Simple demonstrations of the Collections utilities\n",
    "import java.util.*;\n",
    "\n",
    "public class Utilities {\n",
    "  static List<String> list = Arrays.asList(\n",
    "    \"one Two three Four five six one\".split(\" \"));\n",
    "  public static void main(String[] args) {\n",
    "    System.out.println(list);\n",
    "    System.out.println(\"'list' disjoint (Four)?: \" +\n",
    "      Collections.disjoint(list,\n",
    "        Collections.singletonList(\"Four\")));\n",
    "    System.out.println(\n",
    "      \"max: \" + Collections.max(list));\n",
    "    System.out.println(\n",
    "      \"min: \" + Collections.min(list));\n",
    "    System.out.println(\n",
    "      \"max w/ comparator: \" + Collections.max(list,\n",
    "      String.CASE_INSENSITIVE_ORDER));\n",
    "    System.out.println(\n",
    "      \"min w/ comparator: \" + Collections.min(list,\n",
    "      String.CASE_INSENSITIVE_ORDER));\n",
    "    List<String> sublist =\n",
    "      Arrays.asList(\"Four five six\".split(\" \"));\n",
    "    System.out.println(\"indexOfSubList: \" +\n",
    "      Collections.indexOfSubList(list, sublist));\n",
    "    System.out.println(\"lastIndexOfSubList: \" +\n",
    "      Collections.lastIndexOfSubList(list, sublist));\n",
    "    Collections.replaceAll(list, \"one\", \"Yo\");\n",
    "    System.out.println(\"replaceAll: \" + list);\n",
    "    Collections.reverse(list);\n",
    "    System.out.println(\"reverse: \" + list);\n",
    "    Collections.rotate(list, 3);\n",
    "    System.out.println(\"rotate: \" + list);\n",
    "    List<String> source =\n",
    "      Arrays.asList(\"in the matrix\".split(\" \"));\n",
    "    Collections.copy(list, source);\n",
    "    System.out.println(\"copy: \" + list);\n",
    "    Collections.swap(list, 0, list.size() - 1);\n",
    "    System.out.println(\"swap: \" + list);\n",
    "    Collections.shuffle(list, new Random(47));\n",
    "    System.out.println(\"shuffled: \" + list);\n",
    "    Collections.fill(list, \"pop\");\n",
    "    System.out.println(\"fill: \" + list);\n",
    "    System.out.println(\"frequency of 'pop': \" +\n",
    "      Collections.frequency(list, \"pop\"));\n",
    "    List<String> dups =\n",
    "      Collections.nCopies(3, \"snap\");\n",
    "    System.out.println(\"dups: \" + dups);\n",
    "    System.out.println(\"'list' disjoint 'dups'?: \" +\n",
    "      Collections.disjoint(list, dups));\n",
    "    // Getting an old-style Enumeration:\n",
    "    Enumeration<String> e =\n",
    "      Collections.enumeration(dups);\n",
    "    Vector<String> v = new Vector<>();\n",
    "    while(e.hasMoreElements())\n",
    "      v.addElement(e.nextElement());\n",
    "    // Converting an old-style Vector\n",
    "    // to a List via an Enumeration:\n",
    "    ArrayList<String> arrayList =\n",
    "      Collections.list(v.elements());\n",
    "    System.out.println(\"arrayList: \" + arrayList);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[one, Two, three, Four, five, six, one]\n",
    "'list' disjoint (Four)?: false\n",
    "max: three\n",
    "min: Four\n",
    "max w/ comparator: Two\n",
    "min w/ comparator: five\n",
    "indexOfSubList: 3\n",
    "lastIndexOfSubList: 3\n",
    "replaceAll: [Yo, Two, three, Four, five, six, Yo]\n",
    "reverse: [Yo, six, five, Four, three, Two, Yo]\n",
    "rotate: [three, Two, Yo, Yo, six, five, Four]\n",
    "copy: [in, the, matrix, Yo, six, five, Four]\n",
    "swap: [Four, the, matrix, Yo, six, five, in]\n",
    "shuffled: [six, matrix, the, Four, Yo, five, in]\n",
    "fill: [pop, pop, pop, pop, pop, pop, pop]\n",
    "frequency of 'pop': 7\n",
    "dups: [snap, snap, snap]\n",
    "'list' disjoint 'dups'?: true\n",
    "arrayList: [snap, snap, snap]\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输出解释了每种实用方法的行为。请注意由于大小写的缘故，普通版本的 `min()` 和 `max()` 与带有 **String.CASE_INSENSITIVE_ORDER** 比较器参数的版本的区别。\n",
    "\n",
    "<!-- Sorting and Searching Lists -->\n",
    "### 排序和搜索列表\n",
    "\n",
    "用于执行排序和搜索 **List** 的实用工具程序与用于排序对象数组的程序具有相同的名字和方法签名，只不过是 **Collections** 的静态方法而不是 **Arrays** 。 这是一个使用 **Utilities.java** 中的 **list** 数据的示例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/ListSortSearch.java\n",
    "// Sorting/searching Lists with Collections utilities\n",
    "import java.util.*;\n",
    "\n",
    "public class ListSortSearch {\n",
    "  public static void main(String[] args) {\n",
    "    List<String> list =\n",
    "      new ArrayList<>(Utilities.list);\n",
    "    list.addAll(Utilities.list);\n",
    "    System.out.println(list);\n",
    "    Collections.shuffle(list, new Random(47));\n",
    "    System.out.println(\"Shuffled: \" + list);\n",
    "    // Use ListIterator to trim off last elements:\n",
    "    ListIterator<String> it = list.listIterator(10);\n",
    "    while(it.hasNext()) {\n",
    "      it.next();\n",
    "      it.remove();\n",
    "    }\n",
    "    System.out.println(\"Trimmed: \" + list);\n",
    "    Collections.sort(list);\n",
    "    System.out.println(\"Sorted: \" + list);\n",
    "    String key = list.get(7);\n",
    "    int index = Collections.binarySearch(list, key);\n",
    "    System.out.println(\n",
    "      \"Location of \" + key + \" is \" + index +\n",
    "      \", list.get(\" + index + \") = \" +\n",
    "      list.get(index));\n",
    "    Collections.sort(list,\n",
    "      String.CASE_INSENSITIVE_ORDER);\n",
    "    System.out.println(\n",
    "      \"Case-insensitive sorted: \" + list);\n",
    "    key = list.get(7);\n",
    "    index = Collections.binarySearch(list, key,\n",
    "      String.CASE_INSENSITIVE_ORDER);\n",
    "    System.out.println(\n",
    "      \"Location of \" + key + \" is \" + index +\n",
    "      \", list.get(\" + index + \") = \" +\n",
    "      list.get(index));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[one, Two, three, Four, five, six, one, one, Two,\n",
    "three, Four, five, six, one]\n",
    "Shuffled: [Four, five, one, one, Two, six, six, three,\n",
    "three, five, Four, Two, one, one]\n",
    "Trimmed: [Four, five, one, one, Two, six, six, three,\n",
    "three, five]\n",
    "Sorted: [Four, Two, five, five, one, one, six, six,\n",
    "three, three]\n",
    "Location of six is 7, list.get(7) = six\n",
    "Case-insensitive sorted: [five, five, Four, one, one,\n",
    "six, six, three, three, Two]\n",
    "Location of three is 7, list.get(7) = three\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "就像使用数组进行搜索和排序一样，如果使用 **Comparator** 进行排序，则必须使用相同的 **Comparator** 执行 `binarySearch()` 。\n",
    "\n",
    "该程序还演示了 **Collections** 中的 `shuffle()` 方法，该方法随机打乱了 **List** 的顺序。 **ListIterator** 是在打乱后的列表中的特定位置创建的，用于从该位置删除元素，直到列表末尾。\n",
    "\n",
    "<!-- Making a Collection or Map Unmodifiable -->\n",
    "### 创建不可修改的 Collection 或 Map\n",
    "\n",
    "通常，创建 **Collection** 或 **Map** 的只读版本会很方便。 **Collections** 类通过将原始集合传递给一个方法然后返回一个只读版本的集合。 对于 **Collection** （如果不能将 **Collection** 视为更具体的类型）， **List** ， **Set** 和 **Map** ，这类方法有许多变体。这个示例展示了针对每种类型，正确构建只读版本集合的方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/ReadOnly.java\n",
    "// Using the Collections.unmodifiable methods\n",
    "import java.util.*;\n",
    "import onjava.*;\n",
    "\n",
    "public class ReadOnly {\n",
    "  static Collection<String> data =\n",
    "    new ArrayList<>(Countries.names(6));\n",
    "  public static void main(String[] args) {\n",
    "    Collection<String> c =\n",
    "      Collections.unmodifiableCollection(\n",
    "        new ArrayList<>(data));\n",
    "    System.out.println(c); // Reading is OK\n",
    "    //- c.add(\"one\"); // Can't change it\n",
    "\n",
    "    List<String> a = Collections.unmodifiableList(\n",
    "        new ArrayList<>(data));\n",
    "    ListIterator<String> lit = a.listIterator();\n",
    "    System.out.println(lit.next()); // Reading is OK\n",
    "    //- lit.add(\"one\"); // Can't change it\n",
    "\n",
    "    Set<String> s = Collections.unmodifiableSet(\n",
    "      new HashSet<>(data));\n",
    "    System.out.println(s); // Reading is OK\n",
    "    //- s.add(\"one\"); // Can't change it\n",
    "\n",
    "    // For a SortedSet:\n",
    "    Set<String> ss =\n",
    "      Collections.unmodifiableSortedSet(\n",
    "        new TreeSet<>(data));\n",
    "\n",
    "    Map<String,String> m =\n",
    "      Collections.unmodifiableMap(\n",
    "        new HashMap<>(Countries.capitals(6)));\n",
    "    System.out.println(m); // Reading is OK\n",
    "    //- m.put(\"Ralph\", \"Howdy!\");\n",
    "\n",
    "    // For a SortedMap:\n",
    "    Map<String,String> sm =\n",
    "      Collections.unmodifiableSortedMap(\n",
    "        new TreeMap<>(Countries.capitals(6)));\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "[ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,\n",
    "BURUNDI]\n",
    "ALGERIA\n",
    "[BENIN, BOTSWANA, ANGOLA, BURKINA FASO, ALGERIA,\n",
    "BURUNDI]\n",
    "{BENIN=Porto-Novo, BOTSWANA=Gaberone, ANGOLA=Luanda,\n",
    "BURKINA FASO=Ouagadougou, ALGERIA=Algiers,\n",
    "BURUNDI=Bujumbura}\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为特定类型调用 “unmodifiable” 方法不会导致编译时检查，但是一旦发生转换，对修改特定集合内容的任何方法调用都将产生 **UnsupportedOperationException** 异常。\n",
    "\n",
    "在每种情况下，在将集合设置为只读之前，必须使用有意义的数据填充集合。填充完成后，最好的方法是用 “unmodifiable” 方法调用生成的引用替换现有引用。这样，一旦使得内容无法修改，那么就不会冒有意外更改内容的风险。另一方面，此工具还允许将可修改的集合保留为类中的**私有**集合，并从方法调用处返回对该集合的只读引用。所以，你可以在类内修改它，但其他人只能读它。\n",
    "\n",
    "<!-- Synchronizing a Collection or Map -->\n",
    "### 同步 Collection 或 Map\n",
    "\n",
    "**synchronized** 关键字是多线程主题的重要组成部分，更复杂的内容在[第二十四章 并发编程]()中介绍。在这里，只需要注意到 **Collections** 类包含一种自动同步整个集合的方法。 语法类似于 “unmodifiable” 方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/Synchronization.java\n",
    "// Using the Collections.synchronized methods\n",
    "import java.util.*;\n",
    "\n",
    "public class Synchronization {\n",
    "  public static void main(String[] args) {\n",
    "    Collection<String> c =\n",
    "      Collections.synchronizedCollection(\n",
    "        new ArrayList<>());\n",
    "    List<String> list = Collections\n",
    "      .synchronizedList(new ArrayList<>());\n",
    "    Set<String> s = Collections\n",
    "      .synchronizedSet(new HashSet<>());\n",
    "    Set<String> ss = Collections\n",
    "      .synchronizedSortedSet(new TreeSet<>());\n",
    "    Map<String,String> m = Collections\n",
    "      .synchronizedMap(new HashMap<>());\n",
    "    Map<String,String> sm = Collections\n",
    "      .synchronizedSortedMap(new TreeMap<>());\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最好立即通过适当的 “synchronized” 方法传递新集合，如上所示。这样，就不会意外地暴露出非同步版本。\n",
    "\n",
    "<!-- Fail Fast -->\n",
    "#### Fail Fast\n",
    "\n",
    "Java 集合还具有防止多个进程修改集合内容的机制。如果当前正在迭代集合，然后有其他一些进程介入并插入，删除或更改该集合中的对象，则会出现此问题。也许在集合中已经遍历过了那个元素，也许还没有遍历到，也许在调用 `size()` 之后集合的大小会缩小...有许多灾难情景。 Java 集合库使用一种 *fail-fast* 的机制，该机制可以检测到除了当前进程引起的更改之外，其它任何对集合的更改操作。如果它检测到其他人正在修改集合，则会立即生成 **ConcurrentModificationException** 异常。这就是“fail-fast”的含义——它不会在以后使用更复杂的算法尝试检测问题（快速失败）。\n",
    "\n",
    "通过创建迭代器并向迭代器指向的集合中添加元素，可以很容易地看到操作中的 fail-fast 机制，如下所示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/FailFast.java\n",
    "// Demonstrates the \"fail-fast\" behavior\n",
    "import java.util.*;\n",
    "\n",
    "public class FailFast {\n",
    "  public static void main(String[] args) {\n",
    "    Collection<String> c = new ArrayList<>();\n",
    "    Iterator<String> it = c.iterator();\n",
    "    c.add(\"An object\");\n",
    "    try {\n",
    "      String s = it.next();\n",
    "    } catch(ConcurrentModificationException e) {\n",
    "      System.out.println(e);\n",
    "    }\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "java.util.ConcurrentModificationException\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "异常来自于在从集合中获得迭代器之后，又尝试在集合中添加元素。程序的两个部分可能会修改同一个集合，这种可能性的存在会产生不确定状态，因此异常会通知你更改代码。在这种情况下，应先将所有元素添加到集合，然后再获取迭代器。\n",
    "\n",
    "**ConcurrentHashMap** ， **CopyOnWriteArrayList** 和 **CopyOnWriteArraySet** 使用了特定的技术来避免产生 **ConcurrentModificationException** 异常。\n",
    "\n",
    "<!-- Holding References -->\n",
    "## 持有引用\n",
    "\n",
    "**java.lang.ref** 中库包含一组类，这些类允许垃圾收集具有更大的灵活性。特别是当拥有可能导致内存耗尽的大对象时，这些类特别有用。这里有三个从抽象类 **Reference** 继承来的类： **SoftReference** （软引用）， **WeakReference** （弱引用）和 **PhantomReference** （虚引用）继承了三个类。如果一个对象只能通过这其中的一个 **Reference** 对象访问，那么这三种类型每个都为垃圾收集器提供不同级别的间接引用（indirection）。\n",
    "\n",
    "如果一个对象是 *可达的*（reachable），那么意味着在程序中的某个位置可以找到该对象。这可能意味着在栈上有一个直接引用该对象的普通引用，但也有可能是引用了一个对该对象有引用的对象，这可以有很多中间环节。如果某个对象是可达的，则垃圾收集器无法释放它，因为它仍然被程序所使用。如果某个对象是不可达的，则程序无法使用它，那么垃圾收集器回收该对象就是安全的。\n",
    "\n",
    "使用 **Reference** 对象继续保持对该对象的引用，以到达该对象，但也允许垃圾收集器释放该对象。因此，程序可以使用该对象，但如果内存即将耗尽，则允许释放该对象。\n",
    "\n",
    "可以通过使用 **Reference** 对象作为你和普通引用之间的中介（代理）来实现此目的。此外，必须没有对象的普通引用（未包含在 **Reference** 对象中的对象）。如果垃圾收集器发现对象可通过普通引用访问，则它不会释放该对象。\n",
    "\n",
    "按照 **SoftReference** ， **WeakReference** 和 **PhantomReference** 的顺序，每个都比前一个更“弱”，并且对应于不同的可达性级别。软引用用于实现对内存敏感的缓存。弱引用用于实现“规范化映射”（ canonicalized mappings）——对象的实例可以在程序的多个位置同时使用，以节省存储，但不会阻止其键（或值）被回收。虚引用用于调度 pre-mortem 清理操作，这是一种比 Java 终结机制（Java finalization mechanism）更灵活的方式。\n",
    "\n",
    "使用 **SoftReference** 和 **WeakReference** ，可以选择是否将它们放在 **ReferenceQueue** （用于 pre-mortem 清理操作的设备）中，但 **PhantomReference** 只能在 **ReferenceQueue** 上构建。下面是一个简单的演示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/References.java\n",
    "// Demonstrates Reference objects\n",
    "import java.lang.ref.*;\n",
    "import java.util.*;\n",
    "\n",
    "class VeryBig {\n",
    "  private static final int SIZE = 10000;\n",
    "  private long[] la = new long[SIZE];\n",
    "  private String ident;\n",
    "  VeryBig(String id) { ident = id; }\n",
    "  @Override\n",
    "  public String toString() { return ident; }\n",
    "  @Override\n",
    "  protected void finalize() {\n",
    "    System.out.println(\"Finalizing \" + ident);\n",
    "  }\n",
    "}\n",
    "\n",
    "public class References {\n",
    "  private static ReferenceQueue<VeryBig> rq =\n",
    "    new ReferenceQueue<>();\n",
    "  public static void checkQueue() {\n",
    "    Reference<? extends VeryBig> inq = rq.poll();\n",
    "    if(inq != null)\n",
    "      System.out.println(\"In queue: \" + inq.get());\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    int size = 10;\n",
    "    // Or, choose size via the command line:\n",
    "    if(args.length > 0)\n",
    "      size = Integer.valueOf(args[0]);\n",
    "    LinkedList<SoftReference<VeryBig>> sa =\n",
    "      new LinkedList<>();\n",
    "    for(int i = 0; i < size; i++) {\n",
    "      sa.add(new SoftReference<>(\n",
    "        new VeryBig(\"Soft \" + i), rq));\n",
    "      System.out.println(\n",
    "        \"Just created: \" + sa.getLast());\n",
    "      checkQueue();\n",
    "    }\n",
    "    LinkedList<WeakReference<VeryBig>> wa =\n",
    "      new LinkedList<>();\n",
    "    for(int i = 0; i < size; i++) {\n",
    "      wa.add(new WeakReference<>(\n",
    "        new VeryBig(\"Weak \" + i), rq));\n",
    "      System.out.println(\n",
    "        \"Just created: \" + wa.getLast());\n",
    "      checkQueue();\n",
    "    }\n",
    "    SoftReference<VeryBig> s =\n",
    "      new SoftReference<>(new VeryBig(\"Soft\"));\n",
    "    WeakReference<VeryBig> w =\n",
    "      new WeakReference<>(new VeryBig(\"Weak\"));\n",
    "    System.gc();\n",
    "    LinkedList<PhantomReference<VeryBig>> pa =\n",
    "      new LinkedList<>();\n",
    "    for(int i = 0; i < size; i++) {\n",
    "      pa.add(new PhantomReference<>(\n",
    "        new VeryBig(\"Phantom \" + i), rq));\n",
    "      System.out.println(\n",
    "        \"Just created: \" + pa.getLast());\n",
    "      checkQueue();\n",
    "    }\n",
    "  }\n",
    "}\n",
    "/* Output: (First and Last 10 Lines)\n",
    "Just created: java.lang.ref.SoftReference@15db9742\n",
    "Just created: java.lang.ref.SoftReference@6d06d69c\n",
    "Just created: java.lang.ref.SoftReference@7852e922\n",
    "Just created: java.lang.ref.SoftReference@4e25154f\n",
    "Just created: java.lang.ref.SoftReference@70dea4e\n",
    "Just created: java.lang.ref.SoftReference@5c647e05\n",
    "Just created: java.lang.ref.SoftReference@33909752\n",
    "Just created: java.lang.ref.SoftReference@55f96302\n",
    "Just created: java.lang.ref.SoftReference@3d4eac69\n",
    "Just created: java.lang.ref.SoftReference@42a57993\n",
    "...________...________...________...________...\n",
    "Just created: java.lang.ref.PhantomReference@45ee12a7\n",
    "In queue: null\n",
    "Just created: java.lang.ref.PhantomReference@330bedb4\n",
    "In queue: null\n",
    "Just created: java.lang.ref.PhantomReference@2503dbd3\n",
    "In queue: null\n",
    "Just created: java.lang.ref.PhantomReference@4b67cf4d\n",
    "In queue: null\n",
    "Just created: java.lang.ref.PhantomReference@7ea987ac\n",
    "In queue: null\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当运行此程序（将输出重定向到文本文件以查看页面中的输出）时，将会看到对象是被垃圾收集了的，虽然仍然可以通过 **Reference** 对象访问它们（使用 `get()` 来获取实际的对象引用）。 还可以看到 **ReferenceQueue** 始终生成包含 **null** 对象的 **Reference** 。 要使用它，请从特定的 **Reference** 类继承，并为新类添加更多有用的方法。\n",
    "\n",
    "\n",
    "<!-- The WeakHashMap -->\n",
    "### WeakHashMap\n",
    "\n",
    "集合类库中有一个特殊的 **Map** 来保存弱引用： **WeakHashMap** 。 此类可以更轻松地创建规范化映射。在这种映射中，可以通过仅仅创建一个特定值的实例来节省存储空间。当程序需要该值时，它会查找映射中的现有对象并使用它（而不是从头开始创建一个）。 该映射可以将值作为其初始化的一部分，但更有可能的是在需要时创建该值。\n",
    "\n",
    "由于这是一种节省存储空间的技术，因此 **WeakHashMap** 允许垃圾收集器自动清理键和值，这是非常方便的。不能对放在 **WeakHashMap** 中的键和值做任何特殊操作，它们由 map 自动包装在 **WeakReference** 中。当键不再被使用的时候才允许清理，如下所示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/CanonicalMapping.java\n",
    "// Demonstrates WeakHashMap\n",
    "import java.util.*;\n",
    "\n",
    "class Element {\n",
    "  private String ident;\n",
    "  Element(String id) { ident = id; }\n",
    "  @Override\n",
    "  public String toString() { return ident; }\n",
    "  @Override\n",
    "  public int hashCode() {\n",
    "    return Objects.hashCode(ident);\n",
    "  }\n",
    "  @Override\n",
    "  public boolean equals(Object r) {\n",
    "    return r instanceof Element &&\n",
    "      Objects.equals(ident, ((Element)r).ident);\n",
    "  }\n",
    "  @Override\n",
    "  protected void finalize() {\n",
    "    System.out.println(\"Finalizing \" +\n",
    "      getClass().getSimpleName() + \" \" + ident);\n",
    "  }\n",
    "}\n",
    "\n",
    "class Key extends Element {\n",
    "  Key(String id) { super(id); }\n",
    "}\n",
    "\n",
    "class Value extends Element {\n",
    "  Value(String id) { super(id); }\n",
    "}\n",
    "\n",
    "public class CanonicalMapping {\n",
    "  public static void main(String[] args) {\n",
    "    int size = 1000;\n",
    "    // Or, choose size via the command line:\n",
    "    if(args.length > 0)\n",
    "      size = Integer.valueOf(args[0]);\n",
    "    Key[] keys = new Key[size];\n",
    "    WeakHashMap<Key,Value> map =\n",
    "      new WeakHashMap<>();\n",
    "    for(int i = 0; i < size; i++) {\n",
    "      Key k = new Key(Integer.toString(i));\n",
    "      Value v = new Value(Integer.toString(i));\n",
    "      if(i % 3 == 0)\n",
    "        keys[i] = k; // Save as \"real\" references\n",
    "      map.put(k, v);\n",
    "    }\n",
    "    System.gc();\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Key** 类必须具有 `hashCode()` 和 `equals()` ，因为它将被用作散列数据结构中的键。 `hashCode()` 的内容在[附录：理解hashCode和equals方法]()中进行了描述。\n",
    "\n",
    "运行程序，你会看到垃圾收集器每三个键跳过一次。对该键的普通引用也被放置在 **keys** 数组中，因此这些对象不能被垃圾收集。\n",
    "\n",
    "<!-- Java 1.0/1.1 Collections -->\n",
    "## Java 1.0 / 1.1 的集合类\n",
    "\n",
    "不幸的是，许多代码是使用 Java 1.0 / 1.1 中的集合编写的，甚至新代码有时也是使用这些类编写的。编写新代码时切勿使用旧集合。旧的集合类有限，所以关于它们的讨论不多。由于它们是不合时宜的，所以我会尽量避免过分强调一些可怕的设计决定。\n",
    "\n",
    "<!-- Vector & Enumeration -->\n",
    "### Vector 和 Enumeration\n",
    "\n",
    "Java 1.0 / 1.1 中唯一的自扩展序列是 **Vector** ，因此它被用于很多地方。它的缺陷太多了，无法在这里描述（参见《Java编程思想》第1版，可从[www.OnJava8.com](www.OnJava8.com)免费下载）。基本上，你可以将它看作是具有冗长且笨拙的方法名称的 **ArrayList** 。在修订后的 Java 集合库中，**Vector** 已经被调整适配过，因此可以作为 **Collection** 和 **List** 来使用。事实证明这有点不正常，集合类库仍然包含它只是为了支持旧的 Java 代码，但这会让一些人误以为 **Vector** 已经变得更好了。\n",
    "\n",
    "迭代器的 Java 1.0 / 1.1 版本选择创建一个新名称“enumeration”，而不是使用每个人都熟悉的术语（“iterator”）。 **Enumeration** 接口小于 **Iterator** ，只包含两个方法，并且它使用更长的方法名称：如果还有更多元素，则 `boolean hasMoreElements()` 返回 `true` ， `Object nextElement()` 返回此enumeration的下一个元素 （否则会抛出异常）。\n",
    "\n",
    "**Enumeration** 只是一个接口，而不是一个实现，甚至新的类库有时仍然使用旧的 **Enumeration** ，这是不幸的，但通常是无害的。应该总是在自己的代码中使用 **Iterator** ，但要做好准备应对那些提供 **Enumeration** 的类库。\n",
    "\n",
    "此外，可以使用 `Collections.enumeration()` 方法为任何 **Collection** 生成 **Enumeration** ，如下例所示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/Enumerations.java\n",
    "// Java 1.0/1.1 Vector and Enumeration\n",
    "import java.util.*;\n",
    "import onjava.*;\n",
    "\n",
    "public class Enumerations {\n",
    "  public static void main(String[] args) {\n",
    "    Vector<String> v =\n",
    "      new Vector<>(Countries.names(10));\n",
    "    Enumeration<String> e = v.elements();\n",
    "    while(e.hasMoreElements())\n",
    "      System.out.print(e.nextElement() + \", \");\n",
    "    // Produce an Enumeration from a Collection:\n",
    "    e = Collections.enumeration(new ArrayList<>());\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,\n",
    "BURUNDI, CAMEROON, CAPE VERDE, CENTRAL AFRICAN\n",
    "REPUBLIC, CHAD,\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "要生成 **Enumeration** ，可以调用 `elements()` ，然后可以使用它来执行向前迭代。\n",
    "\n",
    "最后一行创建一个 **ArrayList** ，并使用 `enumeration() ` 来将 **ArrayList** 适配为一个 **Enumeration** 。 因此，如果有旧代码需要使用 **Enumeration** ，你仍然可以使用新集合。\n",
    "\n",
    "<!-- Hashtable -->\n",
    "### Hashtable\n",
    "\n",
    "正如你在本附录中的性能比较中所看到的，基本的 **Hashtable** 与 **HashMap** 非常相似，甚至方法名称都相似。在新代码中没有理由使用 **Hashtable** 而不是 **HashMap** 。\n",
    "\n",
    "<!-- Stack -->\n",
    "### Stack\n",
    "\n",
    "之前使用 **LinkedList** 引入了栈的概念。 Java 1.0 / 1.1 **Stack** 的奇怪之处在于，不是以组合方式使用 **Vector** ，而是继承自 **Vector** 。 因此它具有 **Vector** 的所有特征和行为以及一些额外的 **Stack** 行为。很难去知道设计师是否有意识地认为这样做是有用的，或者它是否只是太天真了，无论如何，它在进入发行版之前显然没有经过审查，所以这个糟糕的设计仍然存在（但不要使用它）。\n",
    "\n",
    "这是 **Stack** 的简单演示，向栈中放入枚举中每一个类型的 **String** 形式。它还展示了如何轻松地将 **LinkedList** 用作栈，或者使用在[第十二章：集合]()章节中创建的 **Stack** 类："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/Stacks.java\n",
    "// Demonstration of Stack Class\n",
    "import java.util.*;\n",
    "\n",
    "enum Month { JANUARY, FEBRUARY, MARCH, APRIL,\n",
    "  MAY, JUNE, JULY, AUGUST, SEPTEMBER,\n",
    "  OCTOBER, NOVEMBER }\n",
    "\n",
    "public class Stacks {\n",
    "  public static void main(String[] args) {\n",
    "    Stack<String> stack = new Stack<>();\n",
    "    for(Month m : Month.values())\n",
    "      stack.push(m.toString());\n",
    "    System.out.println(\"stack = \" + stack);\n",
    "    // Treating a stack as a Vector:\n",
    "    stack.addElement(\"The last line\");\n",
    "    System.out.println(\n",
    "      \"element 5 = \" + stack.elementAt(5));\n",
    "    System.out.println(\"popping elements:\");\n",
    "    while(!stack.empty())\n",
    "      System.out.print(stack.pop() + \" \");\n",
    "\n",
    "    // Using a LinkedList as a Stack:\n",
    "    LinkedList<String> lstack = new LinkedList<>();\n",
    "    for(Month m : Month.values())\n",
    "      lstack.addFirst(m.toString());\n",
    "    System.out.println(\"lstack = \" + lstack);\n",
    "    while(!lstack.isEmpty())\n",
    "      System.out.print(lstack.removeFirst() + \" \");\n",
    "\n",
    "    // Using the Stack class from\n",
    "    // the Collections Chapter:\n",
    "    onjava.Stack<String> stack2 =\n",
    "      new onjava.Stack<>();\n",
    "    for(Month m : Month.values())\n",
    "      stack2.push(m.toString());\n",
    "    System.out.println(\"stack2 = \" + stack2);\n",
    "    while(!stack2.isEmpty())\n",
    "      System.out.print(stack2.pop() + \" \");\n",
    "\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "stack = [JANUARY, FEBRUARY, MARCH, APRIL, MAY, JUNE,\n",
    "JULY, AUGUST, SEPTEMBER, OCTOBER, NOVEMBER]\n",
    "element 5 = JUNE\n",
    "popping elements:\n",
    "The last line NOVEMBER OCTOBER SEPTEMBER AUGUST JULY\n",
    "JUNE MAY APRIL MARCH FEBRUARY JANUARY lstack =\n",
    "[NOVEMBER, OCTOBER, SEPTEMBER, AUGUST, JULY, JUNE, MAY,\n",
    "APRIL, MARCH, FEBRUARY, JANUARY]\n",
    "NOVEMBER OCTOBER SEPTEMBER AUGUST JULY JUNE MAY APRIL\n",
    "MARCH FEBRUARY JANUARY stack2 = [NOVEMBER, OCTOBER,\n",
    "SEPTEMBER, AUGUST, JULY, JUNE, MAY, APRIL, MARCH,\n",
    "FEBRUARY, JANUARY]\n",
    "NOVEMBER OCTOBER SEPTEMBER AUGUST JULY JUNE MAY APRIL\n",
    "MARCH FEBRUARY JANUARY\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**String** 形式是由 **Month** 中的枚举常量生成的，使用 `push()` 压入到栈中，然后使用 `pop()` 从栈顶部取出。为了说明一点，将 **Vector** 的操作也在 **Stack** 对象上执行， 这是可能的，因为凭借继承， **Stack** 是 **Vector** 。 因此，可以在 **Vector** 上执行的所有操作也可以在 **Stack** 上执行，例如 `elementAt()` 。\n",
    "\n",
    "如前所述，在需要栈行为时使用 **LinkedList** ，或者从 **LinkedList** 类创建的 **onjava.Stack** 类。\n",
    "\n",
    "<!-- BitSet -->\n",
    "### BitSet\n",
    "\n",
    "**BitSet** 用于有效地存储大量的开关信息。仅从尺寸大小的角度来看它是有效的，如果你正在寻找有效的访问，它比使用本机数组（native array）稍慢。\n",
    "\n",
    "此外， **BitSet** 的最小大小是 **long** ：64位。这意味着如果你要存储更小的东西，比如8位， **BitSet** 就是浪费，如果尺寸有问题，你最好创建自己的类，或者只是用一个数组来保存你的标志。（只有在你创建许多包含开关信息列表的对象时才会出现这种情况，并且只应根据分析和其他指标来决定。如果你做出此决定只是因为您认为 **BitSet** 太大，那么最终会产生不必要的复杂性并且浪费大量时间。）\n",
    "\n",
    "当添加更多元素时，普通集合会扩展， **BitSet**也会这样做。以下示例显示了 **BitSet** 的工作原理："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [
      "java"
     ],
     "id": ""
    }
   },
   "outputs": [],
   "source": [
    "// collectiontopics/Bits.java\n",
    "// Demonstration of BitSet\n",
    "import java.util.*;\n",
    "\n",
    "public class Bits {\n",
    "  public static void printBitSet(BitSet b) {\n",
    "    System.out.println(\"bits: \" + b);\n",
    "    StringBuilder bbits = new StringBuilder();\n",
    "    for(int j = 0; j < b.size() ; j++)\n",
    "      bbits.append(b.get(j) ? \"1\" : \"0\");\n",
    "    System.out.println(\"bit pattern: \" + bbits);\n",
    "  }\n",
    "  public static void main(String[] args) {\n",
    "    Random rand = new Random(47);\n",
    "    // Take the LSB of nextInt():\n",
    "    byte bt = (byte)rand.nextInt();\n",
    "    BitSet bb = new BitSet();\n",
    "    for(int i = 7; i >= 0; i--)\n",
    "      if(((1 << i) &  bt) != 0)\n",
    "        bb.set(i);\n",
    "      else\n",
    "        bb.clear(i);\n",
    "    System.out.println(\"byte value: \" + bt);\n",
    "    printBitSet(bb);\n",
    "\n",
    "    short st = (short)rand.nextInt();\n",
    "    BitSet bs = new BitSet();\n",
    "    for(int i = 15; i >= 0; i--)\n",
    "      if(((1 << i) &  st) != 0)\n",
    "        bs.set(i);\n",
    "      else\n",
    "        bs.clear(i);\n",
    "    System.out.println(\"short value: \" + st);\n",
    "    printBitSet(bs);\n",
    "\n",
    "    int it = rand.nextInt();\n",
    "    BitSet bi = new BitSet();\n",
    "    for(int i = 31; i >= 0; i--)\n",
    "      if(((1 << i) &  it) != 0)\n",
    "        bi.set(i);\n",
    "      else\n",
    "        bi.clear(i);\n",
    "    System.out.println(\"int value: \" + it);\n",
    "    printBitSet(bi);\n",
    "\n",
    "    // Test bitsets >= 64 bits:\n",
    "    BitSet b127 = new BitSet();\n",
    "    b127.set(127);\n",
    "    System.out.println(\"set bit 127: \" + b127);\n",
    "    BitSet b255 = new BitSet(65);\n",
    "    b255.set(255);\n",
    "    System.out.println(\"set bit 255: \" + b255);\n",
    "    BitSet b1023 = new BitSet(512);\n",
    "    b1023.set(1023);\n",
    "    b1023.set(1024);\n",
    "    System.out.println(\"set bit 1023: \" + b1023);\n",
    "  }\n",
    "}\n",
    "/* Output:\n",
    "byte value: -107\n",
    "bits: {0, 2, 4, 7}\n",
    "bit pattern: 101010010000000000000000000000000000000000\n",
    "0000000000000000000000\n",
    "short value: 1302\n",
    "bits: {1, 2, 4, 8, 10}\n",
    "bit pattern: 011010001010000000000000000000000000000000\n",
    "0000000000000000000000\n",
    "int value: -2014573909\n",
    "bits: {0, 1, 3, 5, 7, 9, 11, 18, 19, 21, 22, 23, 24,\n",
    "25, 26, 31}\n",
    "bit pattern: 110101010101000000110111111000010000000000\n",
    "0000000000000000000000\n",
    "set bit 127: {127}\n",
    "set bit 255: {255}\n",
    "set bit 1023: {1023, 1024}\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "随机数生成器用于创建随机 **byte** ， **short** 和 **int** ，并且每个都在 **BitSet** 中转换为相应的位模式。这样可以正常工作，因为 **BitSet** 是64位，所以这些都不会导致它的大小增加，然后创建更大的 **BitSet** 。 请注意， **BitSet** 会根据需要进行扩展。\n",
    "\n",
    "对于可以命名的固定标志集， **EnumSet** （参见[第二十二章：枚举]()章节）通常比 **BitSet** 更好，因为 **EnumSet** 允许操作名称而不是数字位位置，从而可以减少错误。 **EnumSet** 还可以防止意外地添加新的标记位置，这可能会导致一些严重的，难以发现的错误。使用 **BitSet** 而不是 **EnumSet** 的唯一原因是，不知道在运行时需要多少标志，或者为标志分配名称是不合理的，或者需要 **BitSet** 中的一个特殊操作（请参阅 **BitSet** 和 **EnumSet** 的 JDK 文档）。\n",
    "\n",
    "<!-- Summary -->\n",
    "## 本章小结\n",
    "\n",
    "集合可以说是编程语言中最常用的工具。有些语言（例如Python）甚至将基本集合组件（列表，映射和集合）作为内置函数包含在其中。\n",
    "\n",
    "正如在[第十二章：集合]()章节中看到的那样，可以使用集合执行许多非常有用的操作，而不需要太多努力。但是，在某些时候，为了正确地使用它们而不得不更多地了解集合，特别是，必须充分了解散列操作以编写自己的 `hashCode()` 方法（并且必须知道何时需要），并且你必须充分了解各种集合实现，以根据你的需求选择合适的集合。本附录涵盖了这些概念，并讨论了有关集合库的其他有用详细信息。你现在应该已经准备好在日常编程任务中使用 Java 集合了。\n",
    "\n",
    "集合库的设计很困难（大多数库设计问题都是如此）。在 C++ 中，集合类涵盖了许多不同类的基础。这比之前可用的 C++ 集合类更好，但它没有很好地转换为 Java 。在另一个极端，我看到了一个由单个类“collection”组成的集合库，它同时充当线性序列和关联数组。 Java 集合库试图在功能和复杂性之间取得平衡。结果在某些地方看起来有点奇怪。与早期 Java 库中的一些决策不同，这些奇怪的不是事故，而是在基于复杂性的权衡下而仔细考虑的决策。\n",
    "\n",
    "\n",
    "[^1]: **java.util** 中的 **Map** 使用 **Map** 的 `getKey()` 和 `getValue()` 执行批量复制，因此这是有效的。如果自定义 **Map** 只是复制整个 **Map.Entry** ，那么这种方法就会出现问题。\n",
    "\n",
    "[^2]: 虽然当我用这种方式描述它的时候听起来很奇怪而且好像没什么用处，但在[第十九章 类型信息]()章节中已经看到过，这种动态行为也可以非常强大有用。\n",
    "\n",
    "[^3]: 如果这些加速仍然无法满足性能需求，则可以通过编写自己的 **Map** 并将其自定义为特定类型来进一步加速表查找，以避免因向 **对象** 转换而导致的延迟。为了达到更高的性能水平，速度爱好者可以使用 Donald Knuth 的《计算机程序设计艺术（第3卷）：排序与查找》（第二版），将溢出桶列表（overflow bucket lists）替换为具有两个额外优势的阵列：它们可以针对磁盘存储进行优化，并且它们可以节省大部分创建和回收个别记录（individual records）的时间。\n",
    "\n",
    "<!-- 分页 -->\n",
    "\n",
    "<div style=\"page-break-after: always;\"></div>"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 4
}