Java后端常用算法及案例介绍 |21xrx.com

Java后端常用算法及案例介绍

2023-06-17 09:45:48 深夜i -- --

Java后端算法排序算法字符串匹配算法哈希算法

Java作为一种广泛应用于后端开发的编程语言，其常用算法在后端领域发挥了重要作用。本文将介绍一些Java后端开发中常用的算法，并通过案例加以说明和实践。以下是文章中将要涉及的算法和案例。

1. 排序算法

排序算法可谓是算法学习中的入门难点，Java内置的Arrays.sort()方法使用了快速排序算法。以下为快速排序算法Java代码的示例：


public static void quickSort(int[] array, int start, int end) {
  if (start >= end)
    return;
  
  int left = start, right = end, pivot = array[(start + end) / 2];
  while (left <= right) {
    while (left <= right && array[left] < pivot) {
      left++;
    }
    while (left <= right && array[right] > pivot)
      right--;
    
    if (left <= right) {
      int temp = array[left];
      array[left] = array[right];
      array[right] = temp;
      left++;
      right--;
    }
  }
  quickSort(array, start, right);
  quickSort(array, left, end);
}

快速排序算法的时间复杂度平均为O(nlogn)，最坏情况下为O(n^2)。

2. 字符串匹配算法

在Java的Web开发过程中，字符串匹配算法也是经常用到的算法之一。Java中自带的String类及其API中，contains()、indexOf()、replace()等方法底层都使用了字符串匹配算法。以下为KMP字符串匹配算法Java代码的示例：


public static int kmpMatch(String text, String pattern) {
  if (pattern.length() == 0)
    return 0;
  
  int[] next = getNext(pattern);
  for (int i = 0, j = 0, len = text.length(), patternLen = pattern.length(); i < len; ) {
    if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
      j++;
      i++;
      if (j == patternLen)
        return i - j;
      
    }
    if (i < len && text.charAt(i) != pattern.charAt(j)) {
      j = next[j];
    }
  }
  return -1;
}
private static int[] getNext(String pattern) {
  int[] next = new int[pattern.length()];
  next[0] = -1;
  int j = -1, i = 0;
  while (i < pattern.length() - 1) {
    if (j == -1 || pattern.charAt(j) == pattern.charAt(i)) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
  return next;
}

KMP算法的时间复杂度为O(m+n)，其中m为字符串长度，n为匹配模式串的长度。

3. 哈希算法

哈希算法主要用于数据加密、数据一致性校验、数据分片等方面。在Java中，HashMap、HashSet、Hashtable等集合类都使用了哈希算法。以下为Java中哈希表的实现Java代码示例：


public class HashTable
  {
 
  private static final int DEFAULT_INIT_CAPACITY = 8;
  private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  private Entry
  [] table;
 
  private int size;
  private float loadFactor;
  private static class Entry
  {
 
    K key;
    V value;
    Entry
  next;
 
    Entry(K key, V value, Entry
  next)
 
    K getKey()
      return key;
    
    V getValue()
      return value;
    
  }
  public HashTable(int initCapacity, float loadFactor) {
    this.table = new Entry[initCapacity];
    this.loadFactor = loadFactor;
  }
  public HashTable() {
    this(DEFAULT_INIT_CAPACITY, DEFAULT_LOAD_FACTOR);
  }
  public void put(K key, V value) {
    int hash = Objects.hashCode(key);
    int index = hash % table.length;
    Entry
  temp = table[index];
 
    while (temp != null) {
      if (temp.key.equals(key))
        temp.value = value;
        return;
      
      temp = temp.next;
    }
    Entry
  newEntry = new Entry<>(key, value, null);
 
    newEntry.next = table[index];
    table[index] = newEntry;
    size++;
    if (size > table.length * loadFactor) {
      resize();
    }
  }
  private void resize() {
    Entry
  [] oldTable = table;
 
    table = new Entry[table.length * 2];
    for (Entry
  entry : oldTable) {
 
      while (entry != null) {
        Entry
  next = entry.next;
 
        int index = Objects.hashCode(entry.key) % table.length;
        entry.next = table[index];
        table[index] = entry;
        entry = next;
      }
    }
  }
  public V get(K key) {
    int hash = Objects.hashCode(key);
    int index = hash % table.length;
    Entry
  temp = table[index];
 
    while (temp != null) {
      if (temp.key.equals(key))
        return temp.value;
      
      temp = temp.next;
    }
    return null;
  }
  public boolean containsKey(K key) {
    return get(key) != null;
  }
  public boolean remove(K key) {
    int hash = Objects.hashCode(key);
    int index = hash % table.length;
    Entry
  temp = table[index], prev = null;
 
    while (temp != null) {
      if (temp.key.equals(key)) {
        if (prev != null)
          prev.next = temp.next;
         else {
          table[index] = temp.next;
        }
        size--;
        return true;
      }
      prev = temp;
      temp = temp.next;
    }
    return false;
  }
}

以上便是Java后端开发中常用的三种算法及其Java代码示例。

上一篇: idea打包java可执行jar包

下一篇: Java字节码文件：一种神秘的文件类型

评论区

()

相似文章