一個excel(20M)就能幹趴你的poi,你信嗎?

  自從上一篇:后,很巧的是這次又發現一個問題,所以有了這篇文章,還是想沿用上篇的”流水帳“的方式查找問題和解決問題。這篇文章主要是因為使用POI導入一個20M的excel發生了OOM(OutOfMemoryError)異常。說來也慚愧,工作了這麼多年,還真沒導入過這種大小的文件,並且還發生了內存溢出。如果你百度下基本上清一色的告訴你:POI導入excel文件有兩種方式,第一種是用戶模式,這種模式用起來很簡單直觀,可以類比xml的dom方式解析(這裏只針對excel2007,因為2003本身就有最大條數限制並且目前基本用的很少,這裏直接忽略),第二種是event模式,這種通常是網上說的解決POI導入大excel的”萬金油“方法,可以類比為xml的sax解析方式。呵呵,我這篇文章首先就是要干趴這種方法(JVM使用-Xms512m -Xmx512m)。不信你隨便寫一個導入接口,導入如下20M大小的execl看看:鏈接: https://pan.baidu.com/s/1DUrS8ctLPp7Z6imOc1aIUQ 提取碼: hd79 。

  首先,既然要導入大點的excel2007,那麼我們應該稍微了解一下這種文件如何存儲數據,我們百度上可以發現,2007其實就是一個壓縮包,可以直接修改後綴成zip然後解壓打開文件看看,如下

 

  上圖可以看到最大的兩個文件就兩個:sharedStrings.xml和sheet1.xml。其中sheet2.xml這個可以不關注,直接從excel刪掉都沒事,這裏沒刪除主要是沒多大關係,這個excel文件也是測試直接提供給我的。由於sheet2比較小,與這個文章說到的內存溢出並無關係,請不要胡思亂想,被分散了注意。

  直接用大文本編輯工具打開上圖兩個大文件,可以發現sharedString.xml里內容其實就是excel中每個單元格里的字符串內容(数字類型除外),sheet.xml就是每個sheet里的結構xml,了解到這裏基本上就了解了本文章說到問題的基本知識,然後下面進入正題。

  先使用百度中查到的提供的event方式導入excel,代碼如下:

package com.example.utils;

import org.apache.poi.openxml4j.opc.OPCPackage;
import org.apache.poi.xssf.eventusermodel.ReadOnlySharedStringsTable;
import org.apache.poi.xssf.eventusermodel.XSSFReader;
import org.apache.poi.xssf.usermodel.XSSFRichTextString;
import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;
import org.xml.sax.XMLReader;
import org.xml.sax.helpers.DefaultHandler;
import org.xml.sax.helpers.XMLReaderFactory;

import java.io.File;
import java.io.InputStream;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 百度上直接copy過來的
 * XSSF and SAX (Event API)
 */
public abstract class BigDataParseExcelUtil extends DefaultHandler {
    private ReadOnlySharedStringsTable sst;
    private String lastContents;
    private boolean nextIsString;
    private int sheetIndex = -1;
    private List<String> rowlist = new ArrayList<String>();
    private int curRow = 0; // 當前行
    private int curCol = 0; // 當前列索引
    private int preCol = 0; // 上一列列索引
    private int titleRow = 0; // 標題行,一般情況下為0
    private int rowsize = 0; // 列數
    private List excelList = new ArrayList();  //excel全部轉換為list

    // excel記錄行操作方法,以sheet索引,行索引和行元素列表為參數,對sheet的一行元素進行操作,元素為String類型

    public abstract void optRows(int sheetIndex, int curRow,
                                 List<String> rowlist, List excelList) throws SQLException, Exception;

    // 只遍歷一個sheet,其中sheetId為要遍歷的sheet索引,從1開始,1-3

    /**
     * @param filename
     * @param sheetId  sheetId為要遍歷的sheet索引,從1開始,1-3
     * @throws Exception
     */
    public void processOneSheet(String filename, int sheetId) throws Exception {
        OPCPackage pkg = OPCPackage.open(filename);
        XSSFReader r = new XSSFReader(pkg);
        ReadOnlySharedStringsTable strings = new ReadOnlySharedStringsTable(pkg);
        XMLReader parser = fetchSheetParser(strings);
        // rId2 found by processing the Workbook
        // 根據 rId# 或 rSheet# 查找sheet
        InputStream sheet2 = r.getSheet("rId" + sheetId);
        sheetIndex++;
        InputSource sheetSource = new InputSource(sheet2);
        parser.parse(sheetSource);
        sheet2.close();
    }

    @Override
    public void characters(char[] ch, int start, int length)
        throws SAXException {
        // 得到單元格內容的值
        lastContents += new String(ch, start, length);
    }

    public void process(InputStream inputStream) throws Exception {
        OPCPackage pkg = OPCPackage.open(inputStream);
        XSSFReader r = new XSSFReader(pkg);
        ReadOnlySharedStringsTable strings = new ReadOnlySharedStringsTable(pkg);
        XMLReader parser = fetchSheetParser(strings);
        Iterator<InputStream> sheets = r.getSheetsData();
        while (sheets.hasNext()) {
            curRow = 0;
            sheetIndex++;
            InputStream sheet = sheets.next();
            InputSource sheetSource = new InputSource(sheet);
            parser.parse(sheetSource);
            sheet.close();
        }
    }

    /**
     * 遍歷 excel 文件
     */
    public void process(File file) throws Exception {
        OPCPackage pkg = OPCPackage.open(file);
        XSSFReader r = new XSSFReader(pkg);
        ReadOnlySharedStringsTable strings = new ReadOnlySharedStringsTable(pkg);
        XMLReader parser = fetchSheetParser(strings);
        Iterator<InputStream> sheets = r.getSheetsData();
        while (sheets.hasNext()) {
            curRow = 0;
            sheetIndex++;
            InputStream sheet = sheets.next();
            InputSource sheetSource = new InputSource(sheet);
            parser.parse(sheetSource);
            sheet.close();
        }
    }

    public XMLReader fetchSheetParser(ReadOnlySharedStringsTable sst)
        throws SAXException {
        XMLReader parser = XMLReaderFactory.createXMLReader();
        // .createXMLReader("org.apache.xerces.parsers.SAXParser");
        this.sst = sst;
        parser.setContentHandler(this);
        return parser;
    }

    @Override
    public void startElement(String uri, String localName, String name,
                             Attributes attributes) throws SAXException {
        // c => 單元格
        if (name.equals("c")) {
            // 如果下一個元素是 SST 的索引,則將nextIsString標記為true
            String cellType = attributes.getValue("t");
            String rowStr = attributes.getValue("r");
            curCol = this.getRowIndex(rowStr);
            if (cellType != null && cellType.equals("s")) {
                nextIsString = true;
            } else {
                nextIsString = false;
            }
        }
        // 置空
        lastContents = "";
    }

    @Override
    public void endElement(String uri, String localName, String name)
        throws SAXException {
        // 根據SST的索引值的到單元格的真正要存儲的字符串
        // 這時characters()方法可能會被調用多次
        if (nextIsString) {
            try {
                int idx = Integer.parseInt(lastContents);
                lastContents = new XSSFRichTextString(sst.getEntryAt(idx))
                    .toString();
            } catch (Exception e) {
            }
        }
        // v => 單元格的值,如果單元格是字符串則v標籤的值為該字符串在SST中的索引
        // 將單元格內容加入rowlist中,在這之前先去掉字符串前後的空白符
        if (name.equals("v")) {
            String value = lastContents.trim();
            value = value.equals("") ? " " : value;
            int cols = curCol - preCol;
            if (cols > 1) {
                for (int i = 0; i < cols - 1; i++) {
                    rowlist.add(preCol, "");
                }
            }
            preCol = curCol;
            rowlist.add(curCol - 1, value);
        } else {
            // 如果標籤名稱為 row ,這說明已到行尾,調用 optRows() 方法
            if (name.equals("row")) {
                int tmpCols = rowlist.size();
                if (curRow > this.titleRow && tmpCols < this.rowsize) {
                    for (int i = 0; i < this.rowsize - tmpCols; i++) {
                        rowlist.add(rowlist.size(), "");
                    }
                }
                try {
                    optRows(sheetIndex, curRow, rowlist, excelList);
                } catch (SQLException e) {
                    e.printStackTrace();
                } catch (Exception e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
                if (curRow == this.titleRow) {
                    this.rowsize = rowlist.size();
                }
                rowlist.clear();
                curRow++;
                curCol = 0;
                preCol = 0;
            }
        }
    }

    // 得到列索引,每一列c元素的r屬性構成為字母加数字的形式,字母組合為列索引,数字組合為行索引,
    // 如AB45,表示為第(A-A+1)*26+(B-A+1)*26列,45行
    public int getRowIndex(String rowStr) {
        rowStr = rowStr.replaceAll("[^A-Z]", "");
        byte[] rowAbc = rowStr.getBytes();
        int len = rowAbc.length;
        float num = 0;
        for (int i = 0; i < len; i++) {
            num += (rowAbc[i] - 'A' + 1) * Math.pow(26, len - i - 1);
        }
        return (int) num;
    }


}
package com.example.service;

import com.example.utils.BigDataParseExcelUtil;
import org.springframework.stereotype.Service;

import java.io.InputStream;
import java.sql.SQLException;
import java.util.List;

/**
 * @author: rongdi
 * @date:
 */
@Service
public class ExcelService {

    public void import1(InputStream inputStream) throws Exception {

        BigDataParseExcelUtil xlx = new BigDataParseExcelUtil() {
            @Override
            public void optRows(int sheetIndex, int curRow, List<String> rowlist, List excelList)
                throws SQLException {
                System.out.println(rowlist);
            }
        };
        xlx.process(inputStream);
    }


}
package com.example.controller;

import com.example.service.ExcelService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.ResponseBody;
import org.springframework.web.multipart.MultipartFile;

/**
 * @author: rongdi
 * @date:
 */
@Controller
public class ExcelController {

    @Autowired
    private ExcelService excelService;

    @RequestMapping("/excel/import1")
    @ResponseBody
    public String import1(@RequestParam("file") MultipartFile multipartFile) throws Exception {
        excelService.import1(multipartFile.getInputStream());
        return "ok";
    }

}

  使用postman等工具,導入上面說的20M的文件,報錯如下:

   那我們優化一下不使用inputStream,直接使用一個File傳入看看

    public void import2(File file) throws Exception {
        BigDataParseExcelUtil xlx = new BigDataParseExcelUtil() {
            @Override
            public void optRows(int sheetIndex, int curRow, List<String> rowlist, List excelList)
                throws SQLException {
                System.out.println(rowlist);
            }
        };
        xlx.process(file);
    }

    @RequestMapping("/excel/import2")
    @ResponseBody
    public String import2(@RequestParam("file") MultipartFile multipartFile) throws Exception {
        // 延遲解析比率
        ZipSecureFile.setMinInflateRatio(-1.0d);
        File tmp = Files.createTempFile("tmp-", ".xlsx").toFile();
        Files.copy(multipartFile.getInputStream(), Paths.get(tmp.getPath()), StandardCopyOption.REPLACE_EXISTING);
        excelService.import2(tmp);
        return "ok";
    }

  使用postman上傳文件運行效果如下:

 

   這時候就發現很尷尬了,難道是POI自己代碼里就有bug,我們可以使用斷點調試確認一下這個strings里到底是不是全部放了sharedStrings.xml里的內容。

   由上證明就是這個strings裝多了導致內存溢出了,從這裏可以看出網上說使用event事件解析excel的方案基本都是行不通的,哎,我也不懂為啥百度上都是這種答案,難道他們壓根都沒遇到過大數據導入嗎?當然也有可能我冤枉了他們,因為sharedStrings.xml中存放的是每個單元格的字符串內容,這個存放是排重過的,如果雖然excel里單元格很多,但是大多都是整型或者大多都是重複的,那確實可以跳過這一步一路之後會一路暢通了,因為畢竟sax解析xml確實可以節省很多內存。

  從上分析可以看到POI就兩種方式導入:一種是用戶方式寫代碼簡單,基本按順序數格子就好,但是類比dom方式解析xml,很耗內存。第二種事件方式,類比sax方式解析xml確實很省內存,但是POI提供的類里把解析出的大量字符串放入了集合中,還是會導致內存溢出。那麼我們怎麼解決這個問題,這裏很常規的想法是到底這個strings是用來幹啥的,怎麼用的,如果可以保持strings相同邏輯功能的前提下,修改了ReadOnlySharedStringsTable這個類的邏輯,就可以解決這裏的內存溢出了。那麼我們可以直接搜索ReadOnlySharedStringsTable類里所有用到strings的方法上打上斷點,特別是從strings里取值的方法上,然後調大jvm內存避免內存溢出的情況下斷點調試如下

   我們是不是可以直接往strings里添加字符串和獲取字符串的方法那裡替換掉,不要使用strings這個集合存儲所有字符串。但是既然excel里設計成使用一個sharedStrings.xml存放公共的字符串,而不是像csv格式那樣,每次讀一行取一行數據就好了。那麼這個sharedStrings.xml中的數據總要解析出來,總要有個地方存儲裏面的數據,不然怎麼結合sheet.xml的格式獲取到每一行的數據呢?所以這裏就很尷尬了,不能每次解析sharedStrings.xml時不保存每次需要獲取strings的時候,再去解析一下這個xm吧,如果從本文章的xml上來看,要重複解析25W次,效率極其低。現在問題可以簡化成我們需要把sharedStrings.xml解析出的所有字符串放在一個地方,還能方便解析,由於怕內存溢出,肯定不能放在內存中了。那麼這裏就有一些選擇,比如解析出的字符串按加入strings集合的順序放入數據庫,文件,外部存儲或者緩存(限制內存大小,多餘寫入文件)存儲中。然後使用的時候按照索引位置idx去一一取出。本文章先使用臨時文件來放這些數據,因為不想搞那麼複雜,導入任務不管再多複雜的系統中,最終執行的都會是一個單節點,在單節點中先使用本機資源這種就近資源是最方便的。如下直接先複製源碼,然後修改上述說的兩個地方。

package com.example.utils;

import org.apache.poi.ooxml.util.SAXHelper;
import org.apache.poi.openxml4j.opc.OPCPackage;
import org.apache.poi.openxml4j.opc.PackagePart;
import org.apache.poi.ss.usermodel.RichTextString;
import org.apache.poi.util.Removal;
import org.apache.poi.xssf.model.SharedStrings;
import org.apache.poi.xssf.usermodel.XSSFRelation;
import org.apache.poi.xssf.usermodel.XSSFRichTextString;
import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;
import org.xml.sax.XMLReader;
import org.xml.sax.helpers.DefaultHandler;

import javax.xml.parsers.ParserConfigurationException;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.LineNumberReader;
import java.io.PushbackInputStream;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

import static org.apache.poi.xssf.usermodel.XSSFRelation.NS_SPREADSHEETML;

public class ReadOnlySharedStringsTable extends DefaultHandler implements SharedStrings {

    protected final boolean includePhoneticRuns;

    /**
     * An integer representing the total count of strings in the workbook. This count does not
     * include any numbers, it counts only the total of text strings in the workbook.
     */
    protected int count;

    /**
     * An integer representing the total count of unique strings in the Shared String Table.
     * A string is unique even if it is a copy of another string, but has different formatting applied
     * at the character level.
     */
    protected int uniqueCount;

    /**
     * The shared strings table.
     */
    private List<String> strings;

    private File tmp = null;

    FileOutputStream fos = null;

    private int counts;

    private Map<Integer,String> map = new LinkedHashMap<Integer,String>();

    public ReadOnlySharedStringsTable(OPCPackage pkg)
            throws IOException, SAXException {
        this(pkg, true);
    }

    public ReadOnlySharedStringsTable(OPCPackage pkg, boolean includePhoneticRuns)
            throws IOException, SAXException {
        this.includePhoneticRuns = includePhoneticRuns;
        ArrayList<PackagePart> parts =
                pkg.getPartsByContentType(XSSFRelation.SHARED_STRINGS.getContentType());

        // Some workbooks have no shared strings table.
        if (parts.size() > 0) {
            PackagePart sstPart = parts.get(0);
            readFrom(sstPart.getInputStream());
        }
    }

    /**
     * Like POIXMLDocumentPart constructor
     *
     * Calls {@link #ReadOnlySharedStringsTable(PackagePart, boolean)}, with a
     * value of <code>true</code> to include phonetic runs.
     *
     * @since POI 3.14-Beta1
     */
    public ReadOnlySharedStringsTable(PackagePart part) throws IOException, SAXException {
        this(part, true);
    }

    /**
     * Like POIXMLDocumentPart constructor
     *
     * @since POI 3.14-Beta3
     */
    public ReadOnlySharedStringsTable(PackagePart part, boolean includePhoneticRuns)
        throws IOException, SAXException {
        this.includePhoneticRuns = includePhoneticRuns;
        readFrom(part.getInputStream());
    }
    
    /**
     * Read this shared strings table from an XML file.
     *
     * @param is The input stream containing the XML document.
     * @throws IOException if an error occurs while reading.
     * @throws SAXException if parsing the XML data fails.
     */
    public void readFrom(InputStream is) throws IOException, SAXException {
        // test if the file is empty, otherwise parse it
        PushbackInputStream pis = new PushbackInputStream(is, 1);
        int emptyTest = pis.read();
        if (emptyTest > -1) {
            pis.unread(emptyTest);
            InputSource sheetSource = new InputSource(pis);
            try {
                XMLReader sheetParser = SAXHelper.newXMLReader();
                sheetParser.setContentHandler(this);
                sheetParser.parse(sheetSource);
            } catch(ParserConfigurationException e) {
                throw new RuntimeException("SAX parser appears to be broken - " + e.getMessage());
            }
        }
    }

    /**
     * Return an integer representing the total count of strings in the workbook. This count does not
     * include any numbers, it counts only the total of text strings in the workbook.
     *
     * @return the total count of strings in the workbook
     */
    @Override
    public int getCount() {
        return this.count;
    }

    /**
     * Returns an integer representing the total count of unique strings in the Shared String Table.
     * A string is unique even if it is a copy of another string, but has different formatting applied
     * at the character level.
     *
     * @return the total count of unique strings in the workbook
     */
    @Override
    public int getUniqueCount() {
        return this.uniqueCount;
    }

    /**
     * Return the string at a given index.
     * Formatting is ignored.
     *
     * @param idx index of item to return.
     * @return the item at the specified position in this Shared String table.
     * @deprecated use <code>getItemAt</code> instead
     */
    @Removal(version = "4.2")
    @Deprecated
    public String getEntryAt(int idx) {
        /**
         * 這裏就是修改部分了,直接從按行存儲的臨時文件讀取需要的字符串
         */
        String value = map.get(idx + 1);
        if(value == null) {

            return readString(idx,1000,this.uniqueCount);
        } else {
            return value;
        }

    }

    /**
     * 從指定位置讀取size個字符串,這裡是使用局部性原理,每次讀取size個字符串,
     * 以免每次需要讀取文件,性能極低
     * @return
     */
    private String readString(int idx,int size,int numbers) {
        map.clear();
        int currNumber = idx + 1;
        if (currNumber < 0 || currNumber > numbers) {
            return null;
        }
        try {
            FileReader in = new FileReader(tmp);
            LineNumberReader reader = new LineNumberReader(in);
            try {
                String line = "";
                for(int i = 1;i <= numbers;i ++) {
                    line = reader.readLine();
                    if(i >= currNumber && i < currNumber + size) {
                        map.put(i, line);
                    }
                }
            } finally {
                reader.close();
                in.close();
            }
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        return map.get(idx + 1);
    }


    /**
     * Returns all the strings.
     * Formatting is ignored.
     *
     * @return a list with all the strings
     * @deprecated use <code>getItemAt</code> instead
     */
    @Removal(version = "4.2")
    @Deprecated
    public List<String> getItems() {
        return strings;
    }

    @Override
    public RichTextString getItemAt(int idx) {
        return new XSSFRichTextString(getEntryAt(idx));
    }

    //// ContentHandler methods ////

    private StringBuilder characters;
    private boolean tIsOpen;
    private boolean inRPh;

    @Override
    public void startElement(String uri, String localName, String name,
                             Attributes attributes) throws SAXException {
        if (uri != null && ! uri.equals(NS_SPREADSHEETML)) {
            return;
        }

        if ("sst".equals(localName)) {
            String count = attributes.getValue("count");
            if(count != null) this.count = Integer.parseInt(count);
            String uniqueCount = attributes.getValue("uniqueCount");
            if(uniqueCount != null) this.uniqueCount = Integer.parseInt(uniqueCount);
            try {
                tmp = Files.createTempFile("tmp-", ".xlsx").toFile();
            } catch (IOException e) {
                e.printStackTrace();
            }
            //    this.strings = new ArrayList<>(this.uniqueCount);
            characters = new StringBuilder(64);
            try {
                fos = new FileOutputStream(tmp,true);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        } else if ("si".equals(localName)) {
            characters.setLength(0);
        } else if ("t".equals(localName)) {
            tIsOpen = true;
        } else if ("rPh".equals(localName)) {
            inRPh = true;
            //append space...this assumes that rPh always comes after regular <t>
            if (includePhoneticRuns && characters.length() > 0) {
                characters.append(" ");
            }
        }
    }

    @Override
    public void endElement(String uri, String localName, String name) throws SAXException {
        if (uri != null && ! uri.equals(NS_SPREADSHEETML)) {
            return;
        }

        if ("si".equals(localName)) {
         //   strings.add(characters.toString().intern());
            try {
                /**
                 * 這裏就是修改的一部分,這裏直接把字符串按行存入臨時文件
                 */
                counts ++;
                fos.write((characters.toString() + "\n").getBytes());
                if(counts == this.uniqueCount) {
                    fos.close();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        } else if ("t".equals(localName)) {
            tIsOpen = false;
        } else if ("rPh".equals(localName)) {
            inRPh = false;
        }
    }

    /**
     * Captures characters only if a t(ext) element is open.
     */
    @Override
    public void characters(char[] ch, int start, int length) throws SAXException {
        if (tIsOpen) {
            if (inRPh && includePhoneticRuns) {
                characters.append(ch, start, length);
            } else if (! inRPh){
                characters.append(ch, start, length);
            }
        }
    }

}

  然後在自己代碼里把包換成自己的包,替換POI里該類的包,運行JVM堆情況如下毫無壓力

  自此內存溢出問題大功告成!針對使用POI導入大Excel遇到的問題總結如下:

  1)網上給出的方案不管是用戶模式還是事件模式,往往都不能支持大excel的導入

  2)excel本質上是一堆excel的壓縮包(這裏只考慮2007忽略2003)改了個後綴名成xlsx

  3)使用事件導入時應先將上傳文件存入文件,再使用文件OPCPackage.open(file),如果直接傳入輸入流,由於裏面邏輯會將輸入流的所有內容先存入ByteArrayOutputStream 中,這個輸出流實際上是一個內存中的字節流,所以也會導致內存溢出。

  4)用戶模式不用考慮,事件模式會先將sharedString.xml這個大xml解析出來放入一個List中,不管通過什麼方式都繞不開需要解析這個類,因為每個單元格的字符串都放在這個xml中,而要解析這個xml最常規的方法就是保存在內存使用list和map之內的容器存放我相信不會有人會想剛解析出一個xml還要存迴文件中把,這裏基本就繞不開ReadOnlySharedStringsTable或者SharedStringsTable,就算你僥倖繞開了,想自己解析,或許還是重複這兩個類的悲劇,這就是另外一種內存溢出的根源。

  回顧一下上述實現直接把sharedStrings.xml中的內容粗略的保存到文件中,然後再從文件中獲取是屬於很低劣的實現,只能說能滿足不內存溢出,性能方面堪憂!下面直接借鑒easyexcel源碼中用到的ReadCache來實現保存sharedStrings.xml中的內容

package com.example.advanceevent;

import com.example.utils.FileUtils;
import org.ehcache.Cache;
import org.ehcache.CacheManager;
import org.ehcache.config.CacheConfiguration;
import org.ehcache.config.builders.CacheConfigurationBuilder;
import org.ehcache.config.builders.CacheManagerBuilder;
import org.ehcache.config.builders.ResourcePoolsBuilder;
import org.ehcache.config.units.MemoryUnit;
import org.ehcache.core.Ehcache;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.io.File;
import java.util.HashMap;
import java.util.UUID;

/**
 * @author: rongdi
 * @date:
 */
public class ReadCache {

    private static final Logger LOGGER = LoggerFactory.getLogger(Ehcache.class);
    private int index = 0;
    private HashMap<Integer, String> dataMap = new HashMap(1334);
    private static CacheManager fileCacheManager;
    private static CacheConfiguration<Integer, HashMap> fileCacheConfiguration;
    private static CacheManager activeCacheManager;
    private CacheConfiguration<Integer, HashMap> activeCacheConfiguration;
    private Cache<Integer, HashMap> fileCache;
    private Cache<Integer, HashMap> activeCache;
    private String cacheAlias;
    private int cacheMiss = 0;

    public ReadCache(int maxCacheActivateSize) {
        this.activeCacheConfiguration = CacheConfigurationBuilder.newCacheConfigurationBuilder(Integer.class, HashMap.class, ResourcePoolsBuilder.newResourcePoolsBuilder().heap((long)maxCacheActivateSize, MemoryUnit.MB)).withSizeOfMaxObjectGraph(1000000L).withSizeOfMaxObjectSize((long)maxCacheActivateSize, MemoryUnit.MB).build();
        init();
    }

    private void init() {
        this.cacheAlias = UUID.randomUUID().toString();
        this.fileCache = fileCacheManager.createCache(this.cacheAlias, fileCacheConfiguration);
        this.activeCache = activeCacheManager.createCache(this.cacheAlias, this.activeCacheConfiguration);
    }

    public void put(String value) {
        this.dataMap.put(this.index, value);
        if ((this.index + 1) % 1000 == 0) {
            this.fileCache.put(this.index / 1000, this.dataMap);
            this.dataMap = new HashMap(1334);
        }

        ++this.index;
        if (LOGGER.isDebugEnabled() && this.index % 1000000 == 0) {
            LOGGER.debug("Already put :{}", this.index);
        }

    }

    public String get(Integer key) {
        if (key != null && key >= 0) {
            int route = key / 1000;
            HashMap<Integer, String> dataMap = (HashMap)this.activeCache.get(route);
            if (dataMap == null) {
                dataMap = (HashMap)this.fileCache.get(route);
                this.activeCache.put(route, dataMap);
                if (LOGGER.isDebugEnabled() && this.cacheMiss++ % 1000 == 0) {
                    LOGGER.debug("Cache misses count:{}", this.cacheMiss);
                }
            }

            return (String)dataMap.get(key);
        } else {
            return null;
        }
    }

    public void putFinished() {
        if (this.dataMap != null) {
            this.fileCache.put(this.index / 1000, this.dataMap);
        }
    }

    public void destroy() {
        fileCacheManager.removeCache(this.cacheAlias);
        activeCacheManager.removeCache(this.cacheAlias);
    }

    static {
        File cacheFile = FileUtils.createCacheTmpFile();
        fileCacheManager = CacheManagerBuilder.newCacheManagerBuilder().with(CacheManagerBuilder.persistence(cacheFile)).build(true);
        activeCacheManager = CacheManagerBuilder.newCacheManagerBuilder().build(true);
        fileCacheConfiguration = CacheConfigurationBuilder.newCacheConfigurationBuilder(Integer.class, HashMap.class, ResourcePoolsBuilder.newResourcePoolsBuilder().disk(10L, MemoryUnit.GB)).withSizeOfMaxObjectGraph(1000000L).withSizeOfMaxObjectSize(10L, MemoryUnit.GB).build();
    }

}
package com.example.advanceevent;

import org.apache.poi.ooxml.util.SAXHelper;
import org.apache.poi.openxml4j.opc.OPCPackage;
import org.apache.poi.openxml4j.opc.PackagePart;
import org.apache.poi.ss.usermodel.RichTextString;
import org.apache.poi.util.Removal;
import org.apache.poi.xssf.model.SharedStrings;
import org.apache.poi.xssf.usermodel.XSSFRelation;
import org.apache.poi.xssf.usermodel.XSSFRichTextString;
import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;
import org.xml.sax.XMLReader;
import org.xml.sax.helpers.DefaultHandler;

import javax.xml.parsers.ParserConfigurationException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PushbackInputStream;
import java.util.ArrayList;
import java.util.List;

import static org.apache.poi.xssf.usermodel.XSSFRelation.NS_SPREADSHEETML;

public class ReadOnlySharedStringsTable extends DefaultHandler implements SharedStrings {

    protected final boolean includePhoneticRuns;

    /**
     * An integer representing the total count of strings in the workbook. This count does not
     * include any numbers, it counts only the total of text strings in the workbook.
     */
    protected int count;

    /**
     * An integer representing the total count of unique strings in the Shared String Table.
     * A string is unique even if it is a copy of another string, but has different formatting applied
     * at the character level.
     */
    protected int uniqueCount;

    /**
     * 緩存
     */
    ReadCache readCache = new ReadCache(100);

    private int counts;


    public ReadOnlySharedStringsTable(OPCPackage pkg)
            throws IOException, SAXException {
        this(pkg, true);
    }

    public ReadOnlySharedStringsTable(OPCPackage pkg, boolean includePhoneticRuns)
            throws IOException, SAXException {
        this.includePhoneticRuns = includePhoneticRuns;
        ArrayList<PackagePart> parts =
                pkg.getPartsByContentType(XSSFRelation.SHARED_STRINGS.getContentType());

        // Some workbooks have no shared strings table.
        if (parts.size() > 0) {
            PackagePart sstPart = parts.get(0);
            readFrom(sstPart.getInputStream());
        }
    }

    /**
     * Like POIXMLDocumentPart constructor
     *
     * Calls {@link #ReadOnlySharedStringsTable(PackagePart, boolean)}, with a
     * value of <code>true</code> to include phonetic runs.
     *
     * @since POI 3.14-Beta1
     */
    public ReadOnlySharedStringsTable(PackagePart part) throws IOException, SAXException {
        this(part, true);
    }

    /**
     * Like POIXMLDocumentPart constructor
     *
     * @since POI 3.14-Beta3
     */
    public ReadOnlySharedStringsTable(PackagePart part, boolean includePhoneticRuns)
        throws IOException, SAXException {
        this.includePhoneticRuns = includePhoneticRuns;
        readFrom(part.getInputStream());
    }
    
    /**
     * Read this shared strings table from an XML file.
     *
     * @param is The input stream containing the XML document.
     * @throws IOException if an error occurs while reading.
     * @throws SAXException if parsing the XML data fails.
     */
    public void readFrom(InputStream is) throws IOException, SAXException {
        // test if the file is empty, otherwise parse it
        PushbackInputStream pis = new PushbackInputStream(is, 1);
        int emptyTest = pis.read();
        if (emptyTest > -1) {
            pis.unread(emptyTest);
            InputSource sheetSource = new InputSource(pis);
            try {
                XMLReader sheetParser = SAXHelper.newXMLReader();
                sheetParser.setContentHandler(this);
                sheetParser.parse(sheetSource);
            } catch(ParserConfigurationException e) {
                throw new RuntimeException("SAX parser appears to be broken - " + e.getMessage());
            }
        }
    }

    /**
     * Return an integer representing the total count of strings in the workbook. This count does not
     * include any numbers, it counts only the total of text strings in the workbook.
     *
     * @return the total count of strings in the workbook
     */
    @Override
    public int getCount() {
        return this.count;
    }

    /**
     * Returns an integer representing the total count of unique strings in the Shared String Table.
     * A string is unique even if it is a copy of another string, but has different formatting applied
     * at the character level.
     *
     * @return the total count of unique strings in the workbook
     */
    @Override
    public int getUniqueCount() {
        return this.uniqueCount;
    }

    /**
     * Return the string at a given index.
     * Formatting is ignored.
     *
     * @param idx index of item to return.
     * @return the item at the specified position in this Shared String table.
     * @deprecated use <code>getItemAt</code> instead
     */
    @Removal(version = "4.2")
    @Deprecated
    public String getEntryAt(int idx) {
        /**
         * 這裏就是修改部分了,直接從按行存儲的臨時文件讀取需要的字符串
         */
        return readCache.get(idx);

    }

    /**
     * Returns all the strings.
     * Formatting is ignored.
     *
     * @return a list with all the strings
     * @deprecated use <code>getItemAt</code> instead
     */
    @Removal(version = "4.2")
    @Deprecated
    public List<String> getItems() {
        return null;
    }

    @Override
    public RichTextString getItemAt(int idx) {
        return new XSSFRichTextString(getEntryAt(idx));
    }

    //// ContentHandler methods ////

    private StringBuilder characters;
    private boolean tIsOpen;
    private boolean inRPh;

    @Override
    public void startElement(String uri, String localName, String name,
                             Attributes attributes) throws SAXException {
        if (uri != null && ! uri.equals(NS_SPREADSHEETML)) {
            return;
        }

        if ("sst".equals(localName)) {
            String count = attributes.getValue("count");
            if(count != null) this.count = Integer.parseInt(count);
            String uniqueCount = attributes.getValue("uniqueCount");
            if(uniqueCount != null) this.uniqueCount = Integer.parseInt(uniqueCount);
            //    this.strings = new ArrayList<>(this.uniqueCount);
            characters = new StringBuilder(64);
        } else if ("si".equals(localName)) {
            characters.setLength(0);
        } else if ("t".equals(localName)) {
            tIsOpen = true;
        } else if ("rPh".equals(localName)) {
            inRPh = true;
            //append space...this assumes that rPh always comes after regular <t>
            if (includePhoneticRuns && characters.length() > 0) {
                characters.append(" ");
            }
        }
    }

    @Override
    public void endElement(String uri, String localName, String name) throws SAXException {
        if (uri != null && ! uri.equals(NS_SPREADSHEETML)) {
            return;
        }

        if ("si".equals(localName)) {
         //   strings.add(characters.toString().intern());
            readCache.put(characters.toString());
            /**
             * 這裏就是修改的一部分,這裏直接把字符串按行存入臨時文件
             */
            counts ++;
            if(counts == this.uniqueCount) {
                readCache.putFinished();
            }
        } else if ("t".equals(localName)) {
            tIsOpen = false;
        } else if ("rPh".equals(localName)) {
            inRPh = false;
        }
    }

    /**
     * Captures characters only if a t(ext) element is open.
     */
    @Override
    public void characters(char[] ch, int start, int length) throws SAXException {
        if (tIsOpen) {
            if (inRPh && includePhoneticRuns) {
                characters.append(ch, start, length);
            } else if (! inRPh){
                characters.append(ch, start, length);
            }
        }
    }

}

  至此代碼效率有了相當大的提高,而且內存溢出問題也得到解決。詳細測試代碼:https://github.com/rongdi/poi-example.git

  

  

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

東風雷諾武漢工廠正式開張 將投產多款SUV和電動車

2月1日,雷諾汽車宣佈在華合資企業東風雷諾武漢工廠正式開張,該廠耗資8.7億歐元(約合9.42億美元)。

新工廠首款產品將是雷諾科雷嘉緊湊SUV,2016年內還將增添一款規格更大的SUV,預計是和上一代日產奇駿同平臺的車型,2017年則將投產風朗電動車。

東風雷諾武漢工廠年產能為15萬輛,雷諾高管預計未來可能增加一到兩倍。

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

世界地質公園所在 日本再生能源四倍進展 創雙贏局面

文:宋瑞文(加州能源特約撰述)

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

車用電池需求夯!浦項鋼鐵遠赴阿根廷開設鋰礦廠

中國全力發展電動車,車用電池的需求導致鋰價格跳漲,南韓最大鋼鐵供應商浦項鋼鐵(POSCO)看到商機,決定遠赴阿根廷建廠開採鋰資源。

BusinessKorea報導,浦項鋼鐵15日宣布,位於阿根廷薩爾塔(Salta)的廠房已於14日舉行破土儀式,預估每年可淬鍊出2,500公噸的高純度鋰礦,供應各種充電電池、車用電池材料所需。由於每顆車用電池平均需要40公斤的鋰,因此浦項的阿根廷廠一年可供應6萬輛電動車。浦項的廠房坐落於Pozuelos鹽湖,這座湖估計有150萬噸的鋰礦蘊藏量。

全球對鋰的需求量去(2015)年已上升至17萬噸、遠高於2002年的7萬噸,預估2020年市場還將成長至27萬噸。浦項生產的高純度鋰礦將在2020年達到13.5萬噸,約佔整體市場的一半左右。

隨著中國需求快速攀高、當地的鋰礦售價過去幾個月快速飆漲。英國金融時報去年12月15日報導,中國大舉興建電池廠房、對鋰的需求勢必會與日俱增,但採礦商2016年卻又沒有新的產能上線,全球的鋰礦

供需如今已瀕臨短缺邊緣。倫敦顧問機構Benchmark Mineral Intelligence指出,對電動車廠特斯拉(Tesla Motors)的Gigafactory電池廠來說,除了基本電池需求之外,原料是否容易取得將成為最大挑戰,而這也是特斯拉唯一沒有控制權的供應鏈區塊。

根據報導,中國的消費性電子產品與電動車需求攀高,已讓當地的鋰礦售價在過去兩個月內狂飆60%。Benchmark Mineral Intelligence預估,未來光是特斯拉每年就要消耗2.4萬噸的氫氧化鋰(lithium hydroxide),但2014年市場的供應量卻僅有5萬噸。

消息人士指出,特斯拉曾在2014年6月試圖收購加州鋰礦新創公司Simbol Materials,但Simbol自此之後卻遭法院接管,讓併購案無疾而終。之後,特斯拉雖然想與鋰供應大廠Albemarle、FMC Lithium以及SQM簽約,但由於出的價碼太低、沒人點頭答應。目前特斯拉僅與兩家小公司簽有鋰供應協議,但兩者在2020年以前都無法產出足夠多的鋰礦。

(本文內容由授權提供)

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

韓國SK創新2017年起將為奔馳電動汽車供應車載動力電池

韓國SK集團旗下的能源公司SK創新2月17日宣佈,將從2017年開始為奔馳電動汽車供應車載電池,目前已經進入談判的尾聲。

SK創新並未透露協議的細節。該公司是車載電池領域的後起之秀,于2008年開始涉足這一領域,正在全球進行業務擴張。SK創新于2012年在韓國瑞山市建立了首家電池工廠,每年可以滿足1.5萬輛電動汽車電池的供應。

目前,SK創新向起亞汽車與北汽集團供應車載電池。

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

上汽與上海嘉定區合作成立新能源汽車租賃服務公司

2月19日,上汽集團與嘉定區達成合作,簽署《戰略合作備忘錄》、《新能源汽車分時租賃專案合作框架協定》,共同成立一家新能源汽車租賃服務公司,在未來五年內成為同行業國際領先的創新性企業。

公司規劃,2016年基本實現上海市新能源汽車分時租賃服務的全覆蓋,推廣新能源汽車5000輛以上;2018年業務覆蓋國內約100個城市,並探索開拓國際城市,推廣新能源汽車5萬輛以上;2020年業務覆蓋國內主要城市和若干國外典型城市,推廣新能源汽車30萬輛,成為國際上最大的新能源汽車運營服務企業。

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

欲修補與太平洋島國關係 澳洲祭環保新措施

摘錄自2020年3月2日中央社報導

澳洲總理莫里森今(2日)表示,將要求政府機關使用更多資源再生產品。儘管仍拒絕在對抗全球暖化方面多做努力,先前因氣候政策挨轟的坎培拉,現在希望能與太平洋島國修復關係。

莫里森(Scott Morrison)去年不願意擴大減少碳排目標,惹惱太平洋島國領袖。地處低窪的太平洋島國身處氣候變遷前線,正與海平面上升奮戰,部分居民甚至被迫遷徙到地勢較高的土地上。

北京近年來積極和太平洋小國加強經濟關係,其敦促對抗氣候變遷的行動也贏得好感,在在挑戰澳洲過去在太平洋的主導地位。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

氣候變遷 世紀末全球沙灘25%恐消失 海平面上升50公分起跳

環境資訊中心綜合外電;姜唯 編譯;林大利 審校

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

特斯拉將推全新電動車Model S P100D 續航里程可達530公里

據外媒報導,特斯拉將推出Model S P100D車型,新車的綜合性能更強,最大續航里程可達530公里。

Model S P90D與Model S P85D相同,都採用了前後雙電動馬達的配置,但前者進一步強化了電動馬達的馬力輸出表現,安置於前輪的電動馬達可輸出190千瓦的最大功率,後輪的電動馬達則可提供高達370千瓦的最大功率,使得Model S P90D的最大綜合輸出馬力達到驚人的560千瓦。在Model S P90D車型上,特斯拉還新增了動力更加強勁的Ludicrous競速模式,它可讓車輛百公里加速秒數縮短10%,僅需2.8秒即可完成,極速則可達到250公里/小時。

在動力系統方面,Model S P100D車型將搭載功率為100千瓦時的電池里程套件,並搭載雙電機,以及四驅系統。新車的百公里加速時間為2.7秒,最大續航里程可能超過530公里。相較於特斯拉旗下的現款最強車型Model S P90D增加了40公里的續航里程,並縮短了0.6秒的百公里加速時間。

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?

【從今天開始好好學數據結構03】鏈表

目錄

今天我們來聊聊“鏈表(Linked list)”這個數據結構。

在我們上一章中棧與隊列底層都是採用順序存儲的這種方式的,而今天要聊的鏈表則是採用鏈式存儲,鏈表可以說是繼數組之後第二種使用得最廣泛的通用數據結構了,可見其重要性!

相比,鏈表是一種稍微複雜一點的數據結構。對於初學者來說,掌握起來也要比數組稍難一些。這兩個非常基礎、非常常用的數據結構,我們常常將會放到一塊兒來比較。所以我們先來看,這兩者有什麼區別。數組需要一塊連續的內存空間來存儲,對內存的要求比較高。而鏈表恰恰相反,它並不需要一塊連續的內存空間,它通過指針”將一組零散的內存塊串聯起來使用,鏈表結構五花八門,今天我重點給你介紹三種最常見的鏈表結構,它們分別是:單鏈表、雙向鏈表和循環鏈表。

鏈表通過指針將一組零散的內存塊串聯在一起。其中,我們把內存塊稱為鏈表的“結點”。為了將所有的結點串起來,每個鏈表的結點除了存儲數據之外,還需要記錄鏈上的下一個結點的地址。而尾結點特殊的地方是:指針不是指向下一個結點,而是指向一個空地址NULL,表示這是鏈表上最後一個結點。

@

單鏈表

package demo2;

//一個節點
public class Node {

    //節點內容
    int data;
    //下一個節點
    Node next;
    
    public Node(int data) {
        this.data=data;
    }
    
    //為節點追回節點
    public Node append(Node node) {
        //當前節點
        Node currentNode = this;
        //循環向後找
        while(true) {
            //取出下一個節點
            Node nextNode = currentNode.next;
            //如果下一個節點為null,當前節點已經是最後一個節點
            if(nextNode==null) {
                break;
            }
            //賦給當前節點
            currentNode = nextNode;
        }
        //把需要追回的節點追加為找到的當前節點的下一個節點
        currentNode.next=node;
        return this;
    }
    
    //插入一個節點做為當前節點的下一個節點
    public void after(Node node) {
        //取出下一個節點,作為下下一個節點
        Node nextNext = next;
        //把新節點作為當前節點的下一個節點
        this.next=node;
        //把下下一個節點設置為新節點的下一個節點
        node.next=nextNext;
    }
    
    //显示所有節點信息
    public void show() {
        Node currentNode = this;
        while(true) {
            System.out.print(currentNode.data+" ");
            //取出下一個節點
            currentNode=currentNode.next;
            //如果是最後一個節點
            if(currentNode==null) {
                break;
            }
        }
        System.out.println();
    }
    
    //刪除下一個節點
    public void removeNext() {
        //取出下下一個節點
        Node newNext = next.next;
        //把下下一個節點設置為當前節點的下一個節點。
        this.next=newNext;
    }
    
    //獲取下一個節點
    public Node next() {
        return this.next;
    }
    
    //獲取節點中的數據
    public int getData() {
        return this.data;
    }
    
    //當前節點是否是最後一個節點
    public boolean isLast() {
        return next==null;
    }
    
}

單鏈表測試類

package demo2.test;

import demo2.Node;

public class TestNode {
    
    public static void main(String[] args) {
        //創建節點
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        //追加節點
        n1.append(n2).append(n3).append(new Node(4));
        //取出下一個節點的數據
//      System.out.println(n1.next().next().next().getData());
        //判斷節點是否為最後一個節點
//      System.out.println(n1.isLast());
//      System.out.println(n1.next().next().next().isLast());
        
        //显示所有節點內容
        n1.show();
        //刪除一個節點
//      n1.next().removeNext();
        //显示所有節點內容
//      n1.show();
        //插入一個新節點
        Node node = new Node(5);
        n1.next().after(node);
        n1.show();
    }

}

鏈表要想隨機訪問第k個元素,就沒有數組那麼高效了。因為鏈表中的數據並非連續存儲的,所以無法像數組那樣,根據首地址和下標,通過尋址公式就能直接計算出對應的內存地址,而是需要根據指針一個結點一個結點地依次遍歷,直到找到相應的結點。

你可以把鏈表想象成一個隊伍,隊伍中的每個人都只知道自己後面的人是誰,所以當我們希望知道排在第k位的人是誰的時候,我們就需要從第一個人開始,一個一個地往下數。所以,鏈表隨機訪問的性能沒有數組好,需要O(n)的時間複雜度。

雙向鏈表

接下來我們再來看一個稍微複雜的,在實際的軟件開發中,也更加常用的鏈表結構:雙向鏈表。單向鏈表只有一個方向,結點只有一個後繼指針next指向後面的結點。而雙向鏈表,顧名思義,它支持兩個方向,每個結點不止有一個後繼指針next指向後面的結點,還有一個前驅指針prev指向前面的結點。

public class DoubleNode {
    //上一個節點
    DoubleNode pre=this;
    //下一個節點
    DoubleNode next=this;
    //節點數據
    int data;
    
    public DoubleNode(int data) {
        this.data=data;
    }
    
    //增節點
    public void after(DoubleNode node) {
        //原來的下一個節點
        DoubleNode nextNext = next;
        //把新節點做為當前節點的下一個節點
        this.next=node;
        //把當前節點做新節點的前一個節點
        node.pre=this;
        //讓原來的下一個節點作新節點的下一個節點
        node.next=nextNext;
        //讓原來的下一個節點的上一個節點為新節點
        nextNext.pre=node;
    }
    
    //下一個節點
    public DoubleNode next() {
        return this.next;
    }
    
    //上一個節點
    public DoubleNode pre() {
        return this.pre;
    }
    
    //獲取數據
    public int getData() {
        return this.data;
    }
    
}

雙向鏈表測試

import demo2.DoubleNode;

public class TestDoubleNode {

    public static void main(String[] args) {
        //創建節點
        DoubleNode n1 = new DoubleNode(1);
        DoubleNode n2 = new DoubleNode(2);
        DoubleNode n3 = new DoubleNode(3);
        //追加節點
        n1.after(n2);
        n2.after(n3);
        //查看上一個,自己,下一個節點的內容
        System.out.println(n2.pre().getData());
        System.out.println(n2.getData());
        System.out.println(n2.next().getData());
        System.out.println(n3.next().getData());
        System.out.println(n1.pre().getData());
        
    }
    
}

單鏈表VS雙向鏈表

如果我們希望在鏈表的某個指定結點前面插入一個結點或者刪除操作,雙向鏈表比單鏈表有很大的優勢。雙向鏈表可以在O(1)時間複雜度搞定,而單向鏈表需要O(n)的時間複雜度,除了插入、刪除操作有優勢之外,對於一個有序鏈表,雙向鏈表的按值查詢的效率也要比單鏈表高一些。因為,我們可以記錄上次查找的位置p,每次查詢時,根據要查找的值與p的大小關係,決定是往前還是往後查找,所以平均只需要查找一半的數據。

現在,你有沒有覺得雙向鏈表要比單鏈表更加高效呢?這就是為什麼在實際的軟件開發中,雙向鏈表儘管比較費內存,但還是比單鏈表的應用更加廣泛的原因。如果你熟悉Java語言,你肯定用過LinkedHashMap這個容器。如果你深入研究LinkedHashMap的實現原理,就會發現其中就用到了雙向鏈表這種數據結構。實際上,這裡有一個更加重要的知識點需要你掌握,那就是用空間換時間的設計思想。當內存空間充足的時候,如果我們更加追求代碼的執行速度,我們就可以選擇空間複雜度相對較高、但時間複雜度相對很低的算法或者數據結構。相反,如果內存比較緊缺,比如代碼跑在手機或者單片機上,這個時候,就要反過來用時間換空間的設計思路。

循環鏈表

循環鏈表是一種特殊的單鏈表。實際上,循環鏈表也很簡單。它跟單鏈表唯一的區別就在尾結點。我們知道,單鏈表的尾結點指針指向空地址,表示這就是最後的結點了。而循環鏈表的尾結點指針是指向鏈表的頭結點。和單鏈表相比,循環鏈表的優點是從鏈尾到鏈頭比較方便。當要處理的數據具有環型結構特點時,就特別適合採用循環鏈表。比如著名的約瑟夫問題。儘管用單鏈表也可以實現,但是用循環鏈表實現的話,代碼就會簡潔很多。

package demo2;

//一個節點
public class LoopNode {

    //節點內容
    int data;
    //下一個節點
    LoopNode next=this;
    
    public LoopNode(int data) {
        this.data=data;
    }
    
    //插入一個節點做為當前節點的下一個節點
    public void after(LoopNode node) {
        //取出下一個節點,作為下下一個節點
        LoopNode nextNext = next;
        //把新節點作為當前節點的下一個節點
        this.next=node;
        //把下下一個節點設置為新節點的下一個節點
        node.next=nextNext;
    }
    
    //刪除下一個節點
    public void removeNext() {
        //取出下下一個節點
        LoopNode newNext = next.next;
        //把下下一個節點設置為當前節點的下一個節點。
        this.next=newNext;
    }
    
    //獲取下一個節點
    public LoopNode next() {
        return this.next;
    }
    
    //獲取節點中的數據
    public int getData() {
        return this.data;
    }
    
}

循環鏈表測試

package demo2.test;

import demo2.LoopNode;

public class TestLoopNode {

    public static void main(String[] args) {
        LoopNode n1 = new LoopNode(1);
        LoopNode n2 = new LoopNode(2);
        LoopNode n3 = new LoopNode(3);
        LoopNode n4 = new LoopNode(4);
        //增加節點
        n1.after(n2);
        n2.after(n3);
        n3.after(n4);
        System.out.println(n1.next().getData());
        System.out.println(n2.next().getData());
        System.out.println(n3.next().getData());
        System.out.println(n4.next().getData());
    }

}

最後,我們再對比一下數組,數組的缺點是大小固定,一經聲明就要佔用整塊連續內存空間。如果聲明的數組過大,系統可能沒有足夠的連續內存空間分配給它,導致“內存不足(out of memory)”。如果聲明的數組過小,則可能出現不夠用的情況。這時只能再申請一個更大的內存空間,把原數組拷貝進去,非常費時。鏈表本身沒有大小的限制,天然地支持動態擴容,我覺得這也是它與數組最大的區別。

你可能會說,我們Java中的ArrayList容器,也可以支持動態擴容啊?事實上當我們往支持動態擴容的數組中插入一個數據時,如果數組中沒有空閑空間了,就會申請一個更大的空間,將數據拷貝過去,而數據拷貝的操作是非常耗時的。

我舉一個稍微極端的例子。如果我們用ArrayList存儲了了1GB大小的數據,這個時候已經沒有空閑空間了,當我們再插入數據的時候,ArrayList會申請一個1.5GB大小的存儲空間,並且把原來那1GB的數據拷貝到新申請的空間上。聽起來是不是就很耗時?

除此之外,如果你的代碼對內存的使用非常苛刻,那數組就更適合你。因為鏈表中的每個結點都需要消耗額外的存儲空間去存儲一份指向下一個結點的指針,所以內存消耗會翻倍。而且,對鏈表進行頻繁的插入、刪除操作,還會導致頻繁的內存申請和釋放,容易造成內存碎片,如果是Java語言,就有可能會導致頻繁的GC(Garbage Collection,垃圾回收)。

所以,在我們實際的開發中,針對不同類型的項目,要根據具體情況,權衡究竟是選擇數組還是鏈表!

如果本文對你有一點點幫助,那麼請點個讚唄,謝謝~

最後,若有不足或者不正之處,歡迎指正批評,感激不盡!如果有疑問歡迎留言,絕對第一時間回復!

歡迎各位關注我的公眾號,一起探討技術,嚮往技術,追求技術,說好了來了就是盆友喔…

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

小三通海運與一般國際貿易有何不同?

小三通快遞通關作業有哪些?