• 如果hashCode得到的数值大于哈希表的大小该怎么办呢？
  为了保证映射出来的索引数值都落在哈希表上，我们会再次对数值做一个取模的操作，这样就能保证学生姓名一定可以映射到哈希表上了。
  
• 如果学生的数量大于哈希表的大小，即有几位学生的名字会同时映射到哈希表同一个索引下标的位置，此时该怎么办？
  这种同时映射到哈希表同一个索引下标的位置的现象称为哈希碰撞(collisions)。一般有两种解决方法：拉链法和线性探测法。
  1）拉链法
      假设小李和小王在索引1的位置发生了冲突，拉链法是将发生冲突的元素都存储在【链表】中。拉链法就是要选择适当的哈希表大小，既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
      
  2）线性探测法
      线性探测法依靠哈希表中的空位来解决碰撞问题，因此一定要保证哈希表大小 > 数据个数。 例如在冲突的索引1位置放了小李，那么就向下找一个空位放置小王。如图所示：
      
  

• 数组
• set(集合)
• map(映射)
  

• boolean add(E e)	将新元素e加到集合中，返回true；如果e已存在，e不会被加到set中，并返回false。
  ★boolean contains(Object o)	如果集合包含指定的元素，则返回 true 。
  boolean isEmpty()	如果集合不包含元素，则返回 true 。
  boolean remove(Object o)	如果集合中存在o元素，则从该集合中删除o元素。
  int size()	返回集合中的元素个数。
  Object[] toArray()	返回一个包含此集合中所有元素的数组。

  
  

• 常用操作：
  

  V put(K key,V value)	添加键值对元素
  V remove(Object key)	根据指定键删除该键值对元素，并返回该键映射的值
  ★boolean containsKey(Object key)	判断集合中是否有指定键
  ★boolean containsValue(Object value)	判断集合中是否有指定值
  void clear()	删除所有的键值对元素
  boolean isEmpty()	判断集合是否为空
  int size()	返回集合中的键值对的对数（即集合长度）

  【tips】：使用put(K key,V value)添加键值对元素时，如果键重复，则新值会替代该键映射的旧值。
  
• 获取操作：

  V get(Object key)【不是getValue！！！】	根据键，返回值；没有该键的映射就返回null
  ★default V getOrDefault(Object key, V defaultValue)	根据key获取值，如果key不存在，返回defaultValue。 可以用来代替先判断key存不存在，再分情况放value的情况。 if(map.containsKey(key)){     //如果key存在，把对应的value+1     map.put(key,map.get(key)+1); }else{     //如果key不存在，把key加到map中，对应的value为1     map.put(key,1)； } --------等价于下面这行代码--------- map.put(key,map.getOrDefault(key,0)+1);
  Set<K> keySet()	返回包含所有键的Set集合
  Collection<V> values()	返回包含所有值的Collection集合
  Set<Map.Entry<K,V>> entrySet()	返回包含所有整个键值对对象的Set集合

• 思路：数据量比较少且固定，首先考虑使用数组。定义一个数组，先遍历s，记录s中各字符出现的次数；再遍历t，t中字符出现一次，就将hash数组中该字符对应索引的值减1。这样，如果s和t是字母异位词，那么hash数组中的元素就全是0了。

  public boolean isAnagram(String s, String t) {
      //题目已知:s和t仅包含26个小写字母
      int[] hash=new int[26];
      int sLen=s.length(),tLen=t.length();
      //遍历s,统计每个字符出现的次数
      for(int i=0;i<sLen;i++){
          //★每个小写字母减去'a',即a对应下标0，b对应下标1,...,z对应下标25
          hash[s.charAt(i)-'a']++;
      }
      //遍历t,t中的字符出现一次,就将对应索引的值减1
      for(int j=0;j<tLen;j++){
          hash[t.charAt(j)-'a']--;
      }
      //遍历hash数组
      for(int k=0;k<hash.length;k++){
          if(hash[k]!=0){
              return false;
          }
      }
      return true;
  }

• 思路：一开始理解错题意了，正确的题意：magazine要包含ransomNote中的所有字符，且ransomNote中的重复字符要重复包含，可以看成用magazine中的字符来组成ransomNote，且magazine中的每个字符只能用一次。可以定义一个数组hash来记录magazine中所有字符出现的次数(个数)；然后遍历ransomNote，在ransomNote每出现一个字符，就将记录了magazine中所有字符的hash数组对应的字符个数减1，并判断：如果该字符个数小于0，说明magazine中的字符不够用了，即不能包含ransomNote中的所有字符，直接返回false；如果该字符个数大于等于0，继续遍历ransomNote；如果能遍历完ransomNote，说明magazine包含了ransomNote中的所有字符，返回true。

  public boolean canConstruct(String ransomNote, String magazine) {
      int[] have=new int[26];
      //遍历magazine，记录magazine每个字符出现的次数
      for(int i=0;i<magazine.length();i++){
          have[magazine.charAt(i)-'a']++;
      }
      //遍历ransomNote
      for(int j=0;j<ransomNote.length();j++){
          //将ransomNote中出现的字符次数减1
          have[ransomNote.charAt(j)-'a']--;
          //如果小于零说明magazine没有ransomNote需要的字符
          if(have[ransomNote.charAt(j)-'a']<0){
              return false;
          }
      }
      return true;
  }

• ★思路一：字母排序法。因为互为字母异位词的两个字符串包含的字母相同，所以对两个字符串分别排序后得到的字符串一定是相同的，因此可以将排序之后的字符串作为哈希表的键，通过判断其他字符串排序后是否与键相同，来确定是否为字母异位词，进行分组。
  
  具体实现：遍历字符串数组，将拿到的每个字符串转为字符数组，对字符数组进行排序；将排序后的字符数组作为key，判断key是否在map中：
          ①如果key在map中，说明是字母异位词，将key对应的value加到map中；
          ②如果key不在map中，说明不是字母异位词，将其作为新key加到map中。
  返回map中所有的values，即为分组后的字母异位词。

  public List<List<String>> groupAnagrams(String[] strs) {
      //<排序后的字符串,字母异位词分组>
      HashMap<String,List<String>> map=new HashMap<>();
      //遍历字符串数组
      for(String s:strs){
          //将每个字符串转成字符数组
          char[] chs = s.toCharArray();
          //对字符数组进行排序
          Arrays.sort(chs);
          //将排序后的字符数组转成字符串作为key
          String key=String.valueOf(chs);
          //如果key不同，说明不是字母异位词，将 新key和value 保存进map
          if(!map.containsKey(key)){
              List<String> list= new ArrayList<>(); 
              list.add(s);
              map.put(key,list);
          }else{//key相同，说明是字母异位词，将value保存到对应的key
              //通过key获取到对应的字母异位词分组
              map.get(key).add(s);
          }
      }
      //返回所有的字母异位词分组
      return new ArrayList<List<String>>(map.values());
  }

  【tips】这里第一次用到list集合和map映射，要注意一些方法的使用。
• 思路二：常规思路——统计字母出现次数。因为互为字母异位词的两个字符串包含的字母相同，所以两个字符串中的相同字母出现的次数一定是相同的，因此可以将每个字母出现的次数使用字符串表示，作为哈希表的键。★这里要注意的是，我们在统计字母出现的次数时用的是数组，如何将数组作为map的key呢？——我们采用StringBuffer，遍历数组，将字母及其出现的次数拼接成一个字符串，再作为key。
  

  public List<List<String>> groupAnagrams(String[] strs) {
      Map<String, List<String>> map = new HashMap<String, List<String>>();
      for (String str : strs) {
          int[] counts = new int[26];
          int length = str.length();
          for (int i = 0; i < length; i++) {
              counts[str.charAt(i) - 'a']++;
          }
          //★将每个出现次数不为0的字母及其出现次数按顺序拼接成字符串，作为键
          StringBuffer sb = new StringBuffer();
          for (int i = 0; i < 26; i++) {
              if (counts[i] != 0) {
                  sb.append((char)('a' + i));
                  sb.append(counts[i]);
              }
          }
          String key = sb.toString();
          if(!map.containsKey(key)){ 
                          List<String> list= new ArrayList<>(); 
                          list.add(str); 
                          map.put(key,list); 
                  }else{//key相同，说明是字母异位词，将value保存到对应的key 
                          //通过key获取到对应的字母异位词分组 
                          map.get(key).add(str); 
                  }
      }
      return new ArrayList<List<String>>(map.values());
  }

• 思路一(用时太久了。。。不推荐)：受上一道题启发，使用字母排序法来找异位词。定义一个List来记录子串的起始索引；将p排序，然后遍历s，每次截取长度等于p的子串，对子串进行排序，然后与p比较，如果相同，说明该子串是p的异位词，将子串的起始索引加到List中。

  public List<Integer> findAnagrams(String s, String p) {
      //用来记录子串的起始索引
      List<Integer> rslt=new ArrayList<>();
      int pLen=p.length();
      //将p转成字符数组，对其进行排序
      char[] key = p.toCharArray();
      Arrays.sort(key);
      p=String.valueOf(key);
      //遍历s
      for(int i=0;i<=s.length()-pLen;i++){
          //获取从i索引开始的、长度等于p的长度的子串
          //"hamburger".substring(4, 8) returns "urge"
          //"smiles".substring(1, 5) returns "mile"
          String str = s.substring(i,i+pLen);
          //将子串转成字符数组，对其进行排序
          char[] chs = str.toCharArray();
          Arrays.sort(chs);
          //判断子串是否是异位词
          str = String.valueOf(chs);
          //是，将子串起始索引加到rslt中
          if(str.equals(p)){
              rslt.add(i);
          }
      }
      return rslt;
  }

• 思路二：滑动窗口。如果s的长度小于p，则s中一定不存在p的异位词，直接返回空列表rslt。保证s的长度≥p后，先定义一个数组need统计p中各字符出现的次数；定义一个窗口，起始的左右边界都在s的0索引处，移动右边界，将右边界所指字符在need中的次数减一(即抵消p中出现的字符)：
  ①如果此时的次数≥0，说明该字符是组成p的字符，继续向下执行；
  ②如果此时的次数<0，说明该字符不是组成p的字符或该字符出现的次数已经够了(即包含当前字符在内的子串不是p的异位词)，不断收缩左边界，恢复抵消的次数，直到这个负数变成非负数。
  再判断如果窗口长度等于p的长度，该子串就是异位词，将left加到rslt中，移动右边界。

  public List<Integer> findAnagrams(String s, String p) {
      List<Integer> rslt=new ArrayList<>();
      //若s的长度小于p，则s中一定不存在p的异位词。
      if(s.length()<p.length()){
          return rslt;
      }
      //窗口左右边界
      int left=0,right=0;
      int[] need=new int[26];
      //记录p中各字符出现的次数
      for(int i=0;i<p.length();i++){
          need[p.charAt(i)-'a']++;
      }
      //滑动窗口
      while(right<s.length()){
          //抵消p中的次数
          need[s.charAt(right)-'a']--;
          //如果小于0，说明包含当前字符在内的子串不是p的异位词，则收缩左边界
          while(need[s.charAt(right)-'a']<0){
              //★不断收缩左边界，恢复抵消的次数，直到这个负数变成非负数
              need[s.charAt(left)-'a']++;
              left++;
          }
          //如果窗口长度等于p的长度就是可行解
          if(right-left+1==p.length()){
              rslt.add(left);
          }
          right++;
      }
      return rslt;
  }

• 思路一：set集合。根据题意，最终输出的结果是去重的且不考虑顺序，因此优先考虑使用可以去重的set集合。定义两个set集合set和rsltSet，遍历nums1，将元素加到set集合中(相同元素不会被加进去)；然后遍历nums2，判断如果nums2的元素在set中，说明是二者的交集，将其加到rsltSet中。最后把rsltSet转成int[]返回即可。

  public int[] intersection(int[] nums1, int[] nums2) {
      Set<Integer> set=new HashSet<>();
      Set<Integer> rsltSet=new HashSet<>();
      //遍历nums1，将元素加到set集合中(相同元素不会被加进去)
      for(int n:nums1){
          set.add(n);
      }
      //遍历nums2，如果nums2的元素在set中，说明是二者的交集，将其加到rsltSet中
      for(int n:nums2){
          if(set.contains(n)){
              rsltSet.add(n);
          }
      }
      //rsltSet->int[]
      int[] rslt = new int[rsltSet.size()];
      int i = 0;
      for(Integer n:rsltSet){
          rslt[i++]=n;
      }
      return rslt;
  }

• 思路二：双指针法。先将两个数组分别排序，然后定义两个指针分别指向两个数组的第一个元素，遍历两个数组，让双指针遵循“谁小谁先走，相等(交集)一起走，直到走到头”的规则，将相等时的值加到rsltSet中，最后把rsltSet转成int[]返回即可。

  public int[] intersection(int[] nums1, int[] nums2) {
      //排序
      Arrays.sort(nums1);
      Arrays.sort(nums2);
      Set<Integer> rsltSet=new HashSet<Integer>();
      //谁小谁先走，相等一起走，直到走到头
      for(int i=0,j=0; i<nums1.length && j<nums2.length; ){
          if(nums1[i]<nums2[j]){
              i++;
          }else if(nums1[i]>nums2[j]){
              j++;
          }else{
                          //去重
              rsltSet.add(nums1[i]);
              i++;
              j++;
          }
      }
      //set->int[]
      int k=0;
      int[] rslt=new int[rsltSet.size()];
      for(int num:rsltSet){
          rslt[k++]=num;
      }
      return rslt;
  }

• 思路：按题目给出的提示，循环下去要么得到1，要么是无限循环，这就说明非快乐数在求和的过程中，有一个sum值一定会再出现一次。当我们遇到要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了，所以这道题目使用set集合来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum=1为止。还有一个难点就是如何模拟不断获取n的各个位上的数字。★这里不会举一反三了，之前只知道取个位数用n/1%10，取十位数用n/10%10，取百位数用n/100%10...以此类推。其实原理就是利用 int/int 得到的结果是只保留整数部分，而n%10一定能得到n的个位数，所以就是通过“/”，将小数点前移保留整数部分，再用%10获取“个位数”。

  public boolean isHappy(int n) {
      Set<Integer> set=new HashSet<Integer>();
      while(n!=1){
          set.add(n);
          n=getSum(n);            
          if(set.contains(n)){
              return false;
          }
      }
      return true;
  }
  private int getSum(int n){
      int sum=0;
      //不断取n的个位数，直到取到0
      //如12345，每次取到的分别是5,4,3,2,1,0（说明取完了），以因为正整数最高位不可能是0
      while(n!=0){
          sum=sum+(n%10)*(n%10);
          n=n/10;
      }
      return sum;
  }

  代码优化：

  public boolean isHappy(int n) {
      Set<Integer> set=new HashSet<Integer>();
      while(n!=1&&!set.contains(n)){
          set.add(n);
          n=getSum(n);            
      }
      //n=1或者n是重复出现的sum值
      return n==1;
  }
  private int getSum(int n){
      int sum=0;
      while(n!=0){
          int temp=n%10;
          sum+=temp*temp;
          n=n/10;
      }
      return sum;
  }

• 思路：要求数组中的两元素之和等于目标值，可以在遍历数组时用目标值减去当前元素，得到要找的另一个元素temp，判断temp有没有被遍历过，因此我们需要一个集合来保存已遍历过的元素，而这道题还需要保存元素下标，因此想到用map集合作为哈希表，key保存已遍历的元素，value保存对应的下标。

  public int[] twoSum(int[] nums, int target) {
      int[] idxs=new int[2];
      //key:已遍历的元素 value:该元素下标
      Map<Integer,Integer> map=new HashMap<Integer,Integer>();
      for(int i=0;i<nums.length;i++){
          //★要找的另一个数
          int temp=target-nums[i];
          //如果temp已遍历过，说明temp和nums[i]就是符合要求的两个元素
          if(map.containsKey(temp)){
              //保存这两个元素的下标
              idxs[0]=i;
              idxs[1]=map.get(temp);
              break;
          }
          //将当前元素加到map中
          map.put(nums[i],i);
      }
      return idxs;
  }

• 思路：参考上一题两数之和的解题思路，采用分组+哈希表。nums1和nums2为一组，遍历，将二者所有元素之和作为map的key，将和出现的次数作为对应的value；nums3和nums4为一组，遍历，拿 0 减去 二者所有元素的和 去map中匹配key：如果map中有key，说明满足四数之和为0，获取key对应的和出现次数，加到rslt上，返回rslt。
          ★要注意这道题不需要进行去重操作，因此如果n1+n2=1有两组(比如1+0=1，-1+2=1)，因此key=1对应的value是2。那么在求n3+n4时，只要n3+n4=-1，就有两个满足题意的四元组(1+0+n3+n4=0，-1+2+n3+n4=0)。所以在代码中不是rslt++，而是rslt+=对应的value！

  public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
      //key:nums1和nums2元素之和 value:和出现的次数
      Map<Integer,Integer> map=new HashMap<Integer,Integer>();
      int rslt=0;
      //遍历nums1和nums2，将其所有元素和作为key，对应和出现的次数作为value存入map
      for(int n1:nums1){
          for(int n2:nums2){
              int sum=n1+n2;
              if(map.containsKey(sum)){
                  //和出现的次数+1
                  //★注意不能写成map.get(sum)++;
                  map.put(sum,map.get(sum)+1);
              }else{
                  map.put(sum,1);
              }
          }
      }
      //遍历nums3和nums4，拿 0-两数组元素和 去map中匹配key，如果map中有key，说明四数之和为0，获取key对应的和出现次数加到rslt上
      for(int n3:nums3){
          for(int n4:nums4){
              int sum=n3+n4;
              if(map.containsKey(0-sum)){
                  rslt+=map.get(0-sum);
              }
          }
      }
      return rslt;
  }

9.  ★★15. 三数之和

• 思路：排序+双指针法。这道题目不太适合使用哈希法，因为在去重的操作中有很多细节，写起来比较困难；同时程序的执行时间比较长。首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定义指针 left 指向i+1的位置，定义指针 right 指向数组结尾。在数组中找三元组 a、b、c 使得a + b +c =0，这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。然后我们需要解决下面两个问题：
  (一)如何移动left和right呢？
          如果nums[i] + nums[left] + nums[right] > 0 就说明三数之和大了，同时因为数组经过了排序，所以right需要左移，才能让三数之和小一些；如果 nums[i] + nums[left] + nums[right] < 0 说明三数之和小了，left需要右移，才能让三数之和大一些；如果三数之和等于0，说明找到了符合要求的三元组a、b、c，直到left与right相遇为止。
  (二)如何对a、b、c去重呢？
          ①对a(即 nums[i] )去重：a是nums里遍历的元素，如果a重复了那么应该直接跳过去看下一个a。但是是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同呢？二者虽然都是和 nums[i]进行比较，但nums[i + 1]是比较它的下一个元素，nums[i - 1]是比较上一个元素。这里参考一下卡哥的解释(如下图)。
          
          ②★对b和c(即 nums[left] 和 nums[right])的去重：对b和c的去重应该放在找到一个三元组之后，因为这样才能保证第一次找到的三元组可以被放进list。还要注意对b和c的去重要用while而不是if，这里类似收缩窗口的操作。

  public List<List<Integer>> threeSum(int[] nums) {
      List<List<Integer>> rslt=new ArrayList<>();
      Arrays.sort(nums);
      for(int i=0;i<nums.length;i++){
          //因为对nums从小到大排序了，所以如果nums[i]>0，那么往后找一定没有符合题意的三元组，直接return rslt
          if(nums[i]>0){
              return rslt;
          }
          //★对a去重
          if(i>0 && nums[i]==nums[i-1]){
              continue;
          }
          //双指针找b和c
          int left=i+1;
          int right=nums.length-1;
          while(left<right){
              int sum=nums[i]+nums[left]+nums[right];
              if(sum>0){
                  right--;
              }else if(sum<0){
                  left++;
              }else{//★三数之和等于0，先保存三个数，再去重
                  rslt.add(Arrays.asList(nums[i],nums[left],nums[right]));
                  //★对b和c去重应该放在找到一个三元组之后，因为这样才能保证第一次找到的三元组可以被放进list
                  while(left<right&&nums[left]==nums[left+1]){
                      left++;
                  }
                  while(left<right&&nums[right]==nums[right-1]){
                      right--;
                  }
                  //★★★(老是忘了移动双指针)因为上面两个while循环结束后left和right分别指在【最后一个重复元素】的位置上，所以还需要再移动一次指针
                  //也可以这样理解:假如没有重复元素，把三元组加入list后不进入循环，分别移动两个指针
                  left++;
                  right--;
              }
          }
      }
      return rslt;
  }

• 思路：排序+双指针。整体思路与上面的三数之和一样，只不过这里是四个数a、b、c、d，所以只需要多一层for循环。需要注意以下两个问题：
  (一)剪枝操作
  在三数之和时，目标值给定了是0，所以我们将数组排序后，如果当前三个数中最小nums[i]都大于0，那么一定不存在符合题意的三元组；同理四数之和也可以进行这样的剪枝操作，只是这道题的目标值是输入的，可能是个负数，此时不能简单地判断当前最小的nums[i]大于target就直接返回了，因为如果target = -5，而{-4,-1,0,0}，虽然最小的-4大于-5，但是却是我们要找的四元组。因此，这道题的剪枝操作应该加上 target > 0 的判断。
  (二)对a和b去重的细节
  三数之和中我们弄清楚了去重为什么要判断nums[i]与nums[i-1]而不是nums[i+1]，既然是 i - 1 ，就要避免索引越界的问题。这里因为b初始值等于a+1，去重需要判断nums[b]与nums[b-1]，所以跟对a去重时的a>0一样，这里b也要大于b的初始值。
  

  public List<List<Integer>> fourSum(int[] nums, int target) {
      List<List<Integer>> rslt=new ArrayList<>();
      //数组不够4个数，直接返回
      if(nums.length<4){
          return rslt;
      }
      Arrays.sort(nums);
      for(int a=0;a<nums.length;a++){
          //★剪枝操作，类似三数之和里的 nums[i]>0
          if(nums[a]>target && target>0){
              return rslt;
          }
          //对a去重
          if(a>0 && nums[a]==nums[a-1]){
              continue;
          }
          for(int b=a+1;b<nums.length;b++){
              //对b去重，★这里因为b起始等于a+1，去重要判断nums[b]与nums[b-1]，所以跟对a去重时的a>0一样，这里b也要大于b的初始值。
              if (b>a+1 && nums[b]==nums[b-1]) {
                  continue;
              }
              //双指针
              int c=b+1;
              int d=nums.length-1;
              while(c<d){
                  //sum = nums[a]+nums[b]+nums[c]+nums[d]会溢出，所以用long型
                  long sum=(long)nums[a]+nums[b]+nums[c]+nums[d];
                  if(sum>target){
                      d--;
                  }else if(sum<target){
                      c++;
                  }else{
                      rslt.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
                      //对c去重
                      while(c<d&&nums[c]==nums[c+1]){
                          c++;
                      }
                      //对d去重
                      while(c<d&&nums[d]==nums[d-1]){
                          d--;
                      }
                      c++;
                      d--;
                  }
              }
          }
      }
      return rslt;
  }

• 思路：遇到相同元素就更新子串起始位置，每次都要计算子串长度，并更新当前字符"上一次"出现的位置。

  class Solution {
      public int lengthOfLongestSubstring(String s) {
          char[] arr=s.toCharArray();
          //子串起始位置
          int start=0;
          int rslt=0;
          //记录上一个字符出现的下标
          //ascii码有128个(0~127)
          int[] lastIdx=new int[128];
          //★保证各字符第一次出现时都不改变start
          Arrays.fill(lastIdx,-1);
          for(int i=0;i<arr.length;i++){
              //★遇到相同字符就更新start，新位置是上一个位置的下一个位置
              start=Math.max(start,lastIdx[arr[i]]+1);
              rslt=Math.max(rslt,i-start+1);
              //记录当前字符"上一次"出现的位置
              lastIdx[arr[i]]=i;
          }
          return rslt;
      }
  }

• 思路：使用LinkedHashMap，保持插入顺序。LinkedHashMap是HashMap的子类，LinkedHashMap = HashMap + 双向链表，也就是说LinkedHashMap通过维护一个双向链表来保证迭代顺序。

  //LRU缓存:插入元素时，如果满了，就删除最久未使用的元素。
  class LRUCache {
      Integer len;
      //默认在双向链表中按插入顺序排序
      Map<Integer,Integer> map=new LinkedHashMap<>();
      public LRUCache(int capacity) {
          this.len=capacity;
      }
      public int get(int key) {
          if(map.containsKey(key)){
              int val=map.get(key);
              //删除key并重新加入map中，使每次刚访问的key都在链表尾部，最久未使用的在链表头部。
              map.remove(key);
              map.put(key,val);
              return val;
          }
          return -1;
      }
      public void put(int key, int value) {
          if(map.containsKey(key)){
              map.remove(key);
              map.put(key,value);
          }else{
              if(map.size()>=this.len){
                  //删除最久未使用元素，即链表头部元素
                  int oldestKey=map.keySet().iterator().next();
                  map.remove(oldestKey);
                  map.put(key,value);
              }else{
                  map.put(key,value);
              }
          }
      }
  }