计算机内存管理

内存又称主存，是CPU能直接寻址的存储空间，由半导体器件制成。内存的特点是存取速率快。内存是电脑中的主要部件，它是相对于外存而言的。我们平常使用的程序，如Windows操作系统、打字软件、游戏软件等，一般都是安装在硬盘等外存上的，但仅此是不能使用其功能的，必须把它们调入内存中运行，才能真正使用其功能，我们平时输入一段文字，或玩一个游戏，其实都是在内存中进行的。就好比在一个书房里，存放书籍的书架和书柜相当于电脑的外存，而我们工作的办公桌就是内存。通常我们把要永久保存的、大量的数据存储在外存上，而把一些临时的或少量的数据和程序放在内存上，当然内存的好坏会直接影响电脑的运行速度。

数组 - 图1

扩展

字 word
字节 byte
位 bit
字长是指字的长度
1字节=8位(1 byte = 8bit)
1字=2字节(1 word = 2 byte)
64位也就是64bit，也就是8个byte
一个字节的字长是8
一个字的字长为16
bps 是 bits per second 的简称。一般数据机及网络通讯的传输速率都是以「bps」为单位。如56Kbps、100.0Mbps 等等。
Bps 即是Byte per second 的简称。而电脑一般都以Bps 显示速度，如1Mbps 大约等同 128 KBps。
bit 电脑记忆体中最小的单位，在二进位电脑系统中，每一bit 可以代表0 或 1 的数位讯号。
Byte 一个Byte由8 bits 所组成，可代表一个字元(A~Z)、数字(0~9)、或符号(,.?!%&+-/)，是记忆体储存资料的基本单位，至於每个中文字则须要两Bytes。当记忆体容量过大时，位元组这个单位就不够用，因此就有千位元组的单位KB出现，以下乃个记忆体计算单位之间的相关性：
1 Byte = 8 Bits
1 KB = 1024 Bytes
1 MB = 1024 KB
*1 GB = 1024 MB
usb2.0标准接口传输速率。许多人都将“480mbps”误解为480兆/秒。其实，这是错误的，事实上“480mbps”应为“480兆比特/秒”或“480兆位/秒”，它等于“60兆字节/秒”，大家看到差距了吧。
这要从bit和byte说起：bit和byte同译为”比特”，都是数据量度单位，bit=“比特”或“位”。
byte=字节即1byte=8bits,两者换算是1：8的关系。
mbps=mega bits per second(兆位/秒)是速率单位，所以正确的说法应该是说usb2.0的传输速度是480兆位/秒,即480mbps。
mb=mega bytes(兆比、兆字节)是量单位，1mb/s（兆字节/秒）=8mbps（兆位/秒）。
我们所说的硬盘容量是40gb、80gb、100gb，这里的b指是的byte也就是“字节”。
1 kb = 1024 bytes =2^10 bytes
1 mb = 1024 kb = 2^20 bytes
1 gb = 1024 mb = 2^30 bytes
比如以前所谓的56kb的modem换算过来56kbps除以8也就是7kbyte，所以真正从网上下载文件存在硬盘上的速度也就是每秒7kbyte。
也就是说与传输速度有关的b一般指的是bit。
与容量有关的b一般指的是byte。
最后再说一点: usb2.0 480mbps=60mb/s的传输速率还只是理论值，它还要受到系统环境的制约（cpu、硬盘和内存等），其实际读、取写入硬盘的速度约在11～16mb/s。但这也比usb1.1的12mbps(1.5m/s)快了近10倍。
原文参考链接：http://blog.csdn.net/wanlixingzhe/article/details/7107923/

数组——存储和读取

数组是一种线性表数据结构（按前后线性顺序排列），他用一组连续的内存空间，来存储一组具有相同类型的数据（每个值数据类型一样）。
数组 - 图2

读取

每个数组都有一个对应的内存地址，称为数组的开始地址——start_address。
每个元素的内存空间大小——item_size。
数组 - 图3

  1. // 第一个元素地址
  2. start_address
  3. // 第二个元素地址
  4. start_address + item_size * 1
  5. // 第三个元素地址
  6. start_address + item_size * 2
  7. // 第N个元素地址
  8. start_address + item_size * (N - 1)

image.png

自定义List——读取函数

  2. public class YKDArrayList {
  4.   // 此处需要声明一个数组，作为底层存储
  5.   int[] array = new int[20];
  6.   int size = 0;
  8.   public YKDArrayList() {
  9.     //因为还未学习插入，所以暂时内置数据
  10.     this.array[0] = 1;
  11.     this.array[1] = 10;
  12.     this.array[2] = 30;
  13.     this.size = 3;
  14.   }
  16.   // 获取数组的长度
  17.   public int size() {
  18.     return this.size;
  19.   }
  21.   // 数组获取某个索引值
  22.   public int get(int index) {
  23.     return array[index];
  24.   }
  26.   public static void main(String[] args) {
  27.     YKDArrayList arrayList = new YKDArrayList();
  28.     System.out.println(arrayList.get(0));
  29.   }
  30. }

数组插入和删除

尾部插入

  1. start_address + item_size * n  // n 为当前数组的个数

数组 - 图5

中间插入

数组 - 图6
插入地方的后面的数据后移
数组 - 图7

  1. 移动watch movie
  2. 移动have dinner
  3. 插入 afternoon tea

插入开始的地方需要N步，平均步数（1+2+3+…+N)/N 时间复杂度为O（N）。

空间不够

数组 - 图8
数组 - 图9
如果所有的内存空间都不足吗，系统抛出异常——out of memory，内存不足。

数组删除

与插入的操作恰好相反
尾部元素：直接删除
数组 - 图10
中间元素：

  1. 删除中间元素
  2. 右侧元素左移

数组 - 图11
时间复杂度O（N）

自定义List——插入删除函数

  1. public class YKDArrayList {
  3.   // 此处需要声明一个数组，作为底层存储
  4.   int[] array = new int[20];
  5.   int size = 0;
  7.   public YKDArrayList() {
  8.   }
  10.   // 获取数组的长度
  11.   public int size() {
  12.     return this.size;
  13.   }
  15.   // 数组获取某个索引值
  16.   public int get(int index) {
  17.     return this.array[index];
  18.   }
  20.   // 添加元素在末尾 
  21.   public void add(int element) {
  22.     //相当于调用传入this.size
  23.     this.add(this.size, element);
  24.   }
  26.   // 添加元素在中间
  27.   public void add(int index, int element) {
  28.     if (index < 0 || index > this.size) {
  29.       return;
  30.     }
  32.     // 元素依次右移
  33.     for (int i = this.size - 1; i >= index; i--) {
  34.       this.array[i + 1] = this.array[i];
  35.     }
  36.     // 插入元素
  37.     this.array[index] = element;
  38.     // 调整size
  39.     this.size++;
  40.   }
  42.   // 删除元素
  43.   public void remove(int index) {
  44.     if (index < 0 || index > this.size - 1) {
  45.       return;
  46.     }
  48.     // 元素依次左移
  49.     for (int i = index; i < this.size - 1; i++) {
  50.       this.array[i] = this.array[i + 1];
  51.     }
  52.     // 删除最后一个元素
  53.     this.array[this.size - 1] = 0;
  54.     // 调整size
  55.     this.size--;
  56.   }
  58.   public static void main(String[] args) {
  59.     YKDArrayList ykdArrayList = new YKDArrayList();
  60.     ykdArrayList.add(1);
  61.     ykdArrayList.add(2);
  62.     ykdArrayList.add(3);
  63.     ykdArrayList.add(4);
  65.     ykdArrayList.add(0, 5);
  67.     ykdArrayList.remove(3);
  68.   }
  69. }

支持扩容

  2. public class YKDArrayList {
  4.   // 此处需要声明一个数组，作为底层存储
  5.   int[] array = new int[20];
  6.   int size = 0;
  8.   public YKDArrayList() {
  9.   }
  11.   // 获取数组的长度
  12.   public int size() {
  13.     return this.size;
  14.   }
  16.   // 数组获取某个索引值
  17.   public int get(int index) {
  18.     return this.array[index];
  19.   }
  21.   // 添加元素在末尾 
  22.   public void add(int element) {
  23.     //相当于调用传入this.size
  24.     this.add(this.size, element);
  25.   }
  27.   // 添加元素在中间
  28.   public void add(int index, int element) {
  29.     if (index < 0 || index > this.size) {
  30.       return;
  31.     }
  33.     // 支持扩容
  34.     this.judgeMemory(this.size + 1);
  35.     // 元素依次右移
  36.     for (int i = this.size - 1; i >= index; i--) {
  37.       this.array[i + 1] = this.array[i];
  38.     }
  39.     // 插入元素
  40.     this.array[index] = element;
  41.     // 调整size
  42.     this.size++;
  43.   }
  45.   // 删除元素
  46.   public void remove(int index) {
  47.     if (index < 0 || index > this.size - 1) {
  48.       return;
  49.     }
  51.     // 元素依次左移
  52.     for (int i = index; i < this.size - 1; i++) {
  53.       this.array[i] = this.array[i + 1];
  54.     }
  55.     // 删除最后一个元素
  56.     this.array[this.size - 1] = 0;
  57.     // 调整size
  58.     this.size--;
  59.   }
  61.   private void judgeMemory(int size) {
  62.     // 如果内存不满足，则需要扩容
  63.     if (size > this.array.length) {
  64.       // 申明两倍空间
  65.       int[] newArray = new int[this.array.length * 2];
  66.       // 拷贝操作
  67.       this.copy(this.array, newArray);
  68.       // 新数组赋值给原数组
  69.       this.array = newArray;
  70.     }
  71.   }
  73.   // 拷贝操作
  74.   private void copy(int[] source, int[] aim) {
  75.     for (int i = 0; i < source.length; i++) {
  76.       aim[i] = source[i];
  77.     }
  78.   }
  80.   public static void main(String[] args) {
  81.     YKDArrayList ykdArrayList = new YKDArrayList();
  82.     ykdArrayList.add(1);
  83.     ykdArrayList.add(2);
  84.     ykdArrayList.add(3);
  85.     ykdArrayList.add(4);
  87.     ykdArrayList.add(0, 5);
  89.     ykdArrayList.remove(3);
  90.   }
  91. }

总结

优势

  • 查询特别快，时间复杂度O（1）

    劣势

  • 插入删除比较慢，时间复杂度O(N)

  • 需要连续内存空间，并且会申请额外的内存空间便于起扩展，这种数据结构对内存要求比较高，利用率低。

  • ArrayList底层就是利用数组实现的

    demo 回文字符串

    回文字符串：正着读，和反着读都一样的字段串。

    1. madam
    2. 我爱我
    3. 地满红花红满地
    4. 天连碧水碧连天
    5. 洞帘水挂水帘洞
    6. 山果花开花果山
    7. 上海自来水来自海上

    ```java public class Demo {

    // 判断是否为回文字符串 public static boolean isPalindrome(String content) { int i = 0; int end = content.length()-1; while(i<content.length()/2 + 1) {

    1. if (content.charAt(i)!=content.charAt(end)){
    2.   return false;
    3. } 
    4. i++;
    5. end--;

    } return true; }

    public static void main(String[] args) { System.out.println(isPalindrome(“洞帘水挂水帘洞”)); System.out.println(isPalindrome(“上海自来水来自海上”)); System.out.println(isPalindrome(“maddam”)); System.out.println(isPalindrome(“m”)); System.out.println(isPalindrome(“maxcam”)); } }

  1. <a name="cTlhF"></a>
  2. ### 括号匹配
  3. 匹配（）{}括号，有开有合。
  4. ```java
  5. public class Demo {
  7.   // 判断括号是否匹配
  8.   public static boolean isBracketMatch(String content) {
  10.     // 用两个整数存储括号值，出现左括号就+1，出现右括号则-1
  11.     int bracketNum = 0;
  12.     int bigBracketNum = 0;
  14.     for (int i = 0; i < content.length(); i++) {
  15.       char c = content.charAt(i);
  16.       if (c == '(') {
  17.         bracketNum++;
  18.       }
  19.       if (c == '{') {
  20.         bigBracketNum++;
  21.       }
  22.       if (c == ')') {
  23.         bracketNum--;
  24.         // 不能出现负值，负值表示右括号先出现。
  25.         if (bracketNum < 0) {
  26.           return false;
  27.         }
  28.       }
  29.       if (c == '}') {
  30.         bigBracketNum--;
  31.         // 不能出现负值，负值表示右括号先出现。
  32.         if (bigBracketNum < 0) {
  33.           return false;
  34.         }
  35.       }
  36.     } 
  37.     if (bigBracketNum != 0 || bracketNum != 0) {
  38.       return false;
  39.     }
  40.     return true;
  41.   }
  44.   public static void main(String[] args) {
  45.     System.out.println(isBracketMatch("public void run(int a){if(a == 1){System.out.println(a)}}"));
  46.     System.out.println(isBracketMatch("public void run(int a){if(a == 1)System.out.println(a)}}"));
  47.   }
  48. }